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

Его же можно задать матри- Г-1 0 1 0 'l цей В = 1 - 1 0 - 1 v Поскольку ребра изначально не упорядочены, то, например, записывая сначала инцидент­ ность ребра / (1-й столбец), а потом ребра s (2-й столбец), получим матрицу с перестав­ ленными столбцами 1 и 2. Тогда при решении обратной задачи — восстановлении графа по его матрице инцидентности — можно получить граф лишь с точностью до изоморфизма. Поэтому в гра­ фах важно лишь отношение между вершинами (т.е. смежность), а их название и порядок не столь важны. Граф, изображенный на рис. 2.18, задается таблицей инци ­ дентности (табл. 2.2). Рис. 2.18. Графическая интерпрета­ ция графа G, заданного табл. 2.2 Т а б л и ц а 2.2 Таблица инцидентности графа V i Хх *2 Хъ X , *5 *6 X ! х% Х 9 Vi 1 1 0 0 0 0 0 0 0 0 V2 0 1 1 0 0 0 0 1 1 0 Уз 0 0 1 1 0 1 1 0 0 0 у4 0 0 0 1 0 0 0 0 0 1 Уз 0 0 0 0 1 1 0 0 1 0 у 6 1 0 0 0 1 0 1 1 0 1 Матрица инцидентности для него имеет вид Г1 1 0 0 0 0 0 0 0 (Г 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 1 1 0 0 0 “ 0 0 0 1 0 0 0 0 0 1 ' 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 0 1 1 0 1У Этому же рисунку соответствуют таблица и матрица смежно­ сти (табл. 2.3). 86