Во, наочно, цікаво!

Різноманіття.

Ізоморфні графи.

Зауважимо, що граф G (рис. 1) можна зображувати по-різному.

По-перше, зовсім не обов'язково зображувати його ребра прямолінійними. Ми можемо провести будь-які лінії, що з'єднують ті ж самі вершини, що і раніше. Так, граф G можна представити у вигляді, зображеному на рис. 7.

По-друге, ми можемо довільно розташовувати вершини на площині. Наприклад, вершини графа G можна розташувати так, як показано на рис. 8.

Якщо розглядати три графа, зображені на рис. 1, 7 і 8, як графи, що описують хід спортивного турніру, то вони будуть містити в точності одну і ту ж інформацію щодо того, які саме команди вже грали між собою; в певному сенсі це один і той же граф. Ми будемо розмовляти. що два графа- позначимо їх G1 і G2 - ізоморфні, якщо вони відповідають одному і тому ж списку проведених ігор. Іншими словами, якщо графи G1 і G2 ізоморфні. то вони мають одне і те ж число вершин і для будь-яких двох вершин графа G1, скажімо B1 і C1, з'єднаних ребром, відповідні їм вершини B2 і C2 графа G2 теж з'єднані ребром, і назад.

Згідно з цим визначенням, три графа на рис. 1, 7 і 8 ізоморфні (т. Е. Мають один і той же будова), хоча вони і виглядають по-різному.

Нерідко доводиться вирішувати питання про те, чи є два даних графа ізоморфними. Іноді відразу ясно, що це не так. Наприклад, графи, зображені на рис. 9, не можуть бути ізоморфними, тому що вони мають неоднакове число вершин. Не можуть бути ізоморфними і графи рис. 10, так як у них неоднакове число ребер.

Однак для того, щоб показати, що не ізоморфні графи, зображені на рис. 11, потрібно вже кілька більш тонке міркування. Так, можна помітити, що на першому графі є послідовність з восьми суміжних ребер (т. Е. Ребер, попарно мають загальну вершину): (1,2), (2,3), (3,4), (4,8 ), (8,7), (7,6), (6,5), (5,1), що повертається до вихідної вершині, в той час як на другому графі такій послідовності немає. Значить, як би ми не позначили вершини другого графа, ми не зможемо для кожної пари з'єднаних ребром вершин одного графа вказати в другому відповідну пару вершин, теж з'єднаних ребром.

Якщо відразу не видно, як довести, що два графа НЕ ізоморфні, то питання про їх изоморфности може виявитися досить важким. Як приклад розглянемо два графа, зображених на рис. 12; ці графи насправді ізоморфні.