Дискретная математика

139 отображении 2) имеем, что а25=], а а'^2~0, следовательно, тоже не выполнено условие 2) теоремы 5.8 и отображение 2) не будет изоморфизмом рассматриваемых графов. При отображении 3), как и для отображения 1) имеем, что a ^ - l , а a'i2=0, следовательно, отображение 3) не будет изоморфизмом рассматриваемых графов. Осталось проверить отображение 4 ) : 1 2 3 4 5 6 1 5 3 4 2 6 Применяем непосредственно теорему 5.8. Следовательно, нужно сравнить все элементы матриц смежиостей А и Л'графов G и С, чтобы выяснить выполнение условий: ау=а'^р) В матрице А =(aij) имеется 9 элементов, отличных от нуля и равных единице, в матрице А'= (щ') - тоже т о л ь к о 9 элементов равны единице, остальные нули; Л =(А,) = 0^ 0 1 о о о 4' = (4)= 0) 0 1 о о о Проверяем только элементы матриц, которые равны единице, ГТо следовательно имеем: а,4=\. ^ wfl) wf4) ^ 14 Ч1(4)~й,'54~'^> «25=1, j9=l. Продолжая аналогичным образом, получим, что данное отображение явдяется изоморфизмом рассматриваемых графов. Таким образом, убеждаемся, что среди всевозможных 720 отображений только одно является изоморфизмом, но этого достаточно, чтобы убедиться в изоморфности т"рафов G и G § 9. Матрица инциденций Пусть G - граф с множеством вершин F={v,,v2,...,v „} и множеством ребер X={xj,x2,...,x, „}. Графу G ставим в соответствие лгатрпг/у инциденций ^ = (a^j) размером пхт, (i.j) -й элемент которой равен: