Изоморфный – той же формы
Опр: Пусть граф G1(V1, E1) и G2(V2 E2). Биективное f: V1 -> V2 называется изоморфизмом G1 на G2 если любые u,v число ребер coeдиняющих вершины u и v в G1 = числу ребер соед. f(u) и f(v) в G2 . Для обычн. графов изом. – это биекция, харак-ся след. свойством: произв. вершины u и v смежны только тогда, когда вершины и смежны f(u) и f(v) в G2. 
если существует изоморфизм G1 на G2
Т-ма:Изоморфизм это отношение эквивалентности на множестве графов Док-во: Основано на том, что тождественное отображение биек., бие-ое обратимо, а обратные бие-ы. Композиция бие-ых отношений биек..
Т-ма.Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одновременными перестановками строк и столбцов.
Док-во:Мультиграфы G и G’ изоморфны, когда их матрицы инцидентности получаются друг из друга путем перестановки строк и столбцов.
Принцип изоморфизма.
Чтобы показать, что два графа изоморфны, нужно найти изоморфизм одного графа в другой. Чтобы показать что графы не изоморфны, нужно найти свойства одного графа, не выполняющиеся в другом.
