Теория графов и комбинаторика

, еоля 3 ^ . ' V - ^ W \/1Г(;,гЛ<е\/'С Л }б Х Геом0тричвс:,л изоморфнооть графов означает возможность наложения их диаграмм друг на друга без разрывов и оклаивакий. Теорема 4 . 1 . Изоморфнооть графов являетоя отношением экви валентнооти на множестве графов. Доказательство. Покажем, что отношение изоморфнооти реф- лекоивно, оишетрично и т1»нэитивно. РеФланоивнооть. о- . Дейотвг"Г9льно, изоморфиз­ мом являетоя тоадеотввнное гфзобразование J '•V - > V , для которого '^V'SV Симметвичнооть. У Д е й с т в и т е л ь н о , пуоть <? 'V И . Тогда • Провг-пим это. Пуоть ^ Обозначим . Еили W2 а ыЩ в графеМ, чй Тс ом в графе G , т . к . в противном случае в оилу того что f являетоя изоморфизмом, в е рш • IClTc); ^ были бн Н0ОМЗЖНН в графеН . Но $(^Г1)~^{$''ц)Тс)) - v>{_, . Таким образом, предположение о не- омежнботи вершин i V iWi ) и i противоречит уоловию W i ом Ufy . Аналогично можно раоомотреть олучай, когда ti/c не ом и т;оказать неймежнооть вершин ^Транзитйвноотъ.V F , g , Н Дяя доказа­ тельства иаомсрфности графов F к Н нужно установить оущеотво- В(энив ооответотвущего иасморфизма у •Легко проверить, что я качестве Y можно ваять композицию 5" и f ^ f • K i теорвда 4 . 1 следует, что отношение изоморфнооти разбя~ вает множество яоех графов на классы эквивалентности. Поэтому каждый граф является предотаЕлтелем целого класса изомо'рфных друг ДЕугу графов. Таким образом, введя понятие изоморфнооти 1?рафов, ш'подучим возможность понятие равенства графов заме­ нить понятием равеноФва клаосов. Пример. На рис.4.x н 4 . 2 показана пары изомсрфннз; и не изоморфных графов. Отнокать IISOMO];^3U В первом случае и дока- вать оюутоФвие изоморфизма в о втором предлагается читателя. В ) Й о . 4 Л Б ) а ) ^ЧБ); Еио.4.2