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

определении матрицы смежности (как графа с кратными ребрами, так и без них) не всегда возможно определить по матрице смеж­ ности ориентированный граф или нет. В матрицах инцидентности такой проблемы нет, так как нали­ чие элемента вида -1 является критерием ориентированности графа. Для матрицы смежности несимметричность может являться до­ статочным условием ориентированности, но не критерием. На­ пример, графу с матрицей смежности ^0 1 п о может соответство­ вать отрезок К, V 2 (и две вершины) — неориентированный граф или кольцо с двумя ребрами V={(VU К2); (У2, К,)} — орграф. Это существенный недостаток, и возник он как раз при попытке оп­ ределения матрицы смежности для графа с кратными ребрами. Поэтому для задания ориентированного графа с помощью матри­ цы смежности (если она получается симметричной) надо или ука­ зывать это отдельно, например Лор, или у любого элемента мат­ рицы написать «-». Задача 19. Пусть граф G задан матрицей смежности А. Постро­ ить диаграмму этого графа, если '0 1 0 1 0 г 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 1 1 1 0 Решение. Поскольку матрица А несимметрична (например, °35 *■ а 5 з) и указания на ориентированность нет, А не может яв ­ ляться матрицей смежности реального графа. Задача 20. Пусть граф G задан матрицей смежности А. Постро­ ить диаграмму этого графа, если 0 0 0 1 0 0 ' 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 0 1 0 0 1 0 1 1 0 1 0 1 1 0 Решение. Диаграмму графа, имеющего шесть вершин, предста­ вим на рис. 2.19. Любой ориентированный граф является бинарным отношени­ ем А под V, где V —множество вершин графа, а пары из X — ребра. 88