Спирина, М.С. Дискретная математика

Та б л иц а 2.3 Таблица смежности графа G V, Vj V, V2 Vi V4 Vs Vs V, 0 1 0 1 0 1 V2 1 0 1 1 0 1 V3 0 1 0 1 1 1 V4 1 1 1 0 0 1 Vs 0 0 1 0 0 1 V6 1 1 1 1 1 0 А = ''0 1 0 1 0 1'' 1 0 1 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 0 0 1 0 0 1 1 1 1 1 1 0 Граф с кратными ребрами (особенно орграф) сложно задать с помощью матрицы смежности. Сделаем это формально. Если граф неориентированный, то справедливо ау = а,, и равно кратности ребра ( Vj, V^). В частности, если /= / , то a:j — число петель при V,. Недостаток подобного подхода заключается в том, что остается неучтенным взаимное расположение кратных ребер. Так, ребра могут переплетаться между собой, что, к сожалению, не отразит­ ся на матрице смежности. Заметим, что для ориентированного графа данное определе­ ние графа без кратных ребер является частным случаем графа с кратными ребрами при кратности любого ребра, равной 1 или 0. Очевидно, что для двух вершин V, и V, (/ * J) существуют две принципиальные возможности: если все ребра выходят из одной и входят в другую вершину или если для каждой вершины суще­ ствуют как входящие, так и исходящие ребра. Пусть полная кратность ребра равна п, при этом из вершины Vt в вершину Vj исходят т< п ребер, а из Vj в Vt исходят п - т ребер. Тогда в клетке напишем т, а в клетке ajt напишем п - т. Если есть кратные петли, то все они связаны с одной вершиной Vh поэтому в клетке аи напишем кратность петли при V,. Такому заданию графа присущи те же недостатки, что и не­ ориентированному, и еще неучет взаимного расположения направ­ лений. Однако главным недостатком служит то, что при таком 87