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

Из изложенного следует, что если графы и H^C^iY) jtaoMopIiiia, то фактичеисн устанавливается взаимно однозначное оо- о'ГветотЕив не тол'ько между их зершнагла, но и м е в д их рвйрами. It09T0(jty можно дать второе опрвделеше нзомор^нооти. Графы ^ и Н называются изоморфными, воли оувдептвуит взаимно однозне^хные ото­ бражения , ооглаоозанша ол0;1ую11аш ойразом*. Изоморфизм ор1ентирозанных •"рафоз определяотоя также с учетом ориектшГкШ ду г . ^4.2. Необходимые условия изомо'о.тжооти гпаТюв ТГриэадем рад простых необходимых уоловий изоморфное®- грпфов. Теорема 4 . 2 . Пусгь , Н = CW ,Y ) - произволь­ ные гра^м. Тогда, е о г ; /г^'Н ^ то MS-^CS- . .Показател-ботзо. Пуо^ь J.* V->W - изоморфизм лжя пары графов (гиИй (?^ = СViJ!<•<)-произволышй подграф . Тогда Определим мноявстзо Y^ ребэр r p a j a =• ), оледуюим ойрааом; ; ( i f 'Wt ) ,5*Vt iTp J е . X j . Очезидао,У,C Y . так как изоморфизм i оохрашет омекнооть. Слодовательно, ~ =(Ui,Yj) являетоя Т10дгра(1)0м И(Н<СН) ' Ооталось доказать, здо пойтроепны(1 подграф Н^ ; joMopJiea подграс1|у G . Легко заме­ тить, что изоморриамом, устанавливающим изомор|)нооть графов я Н| , является отображение • првдотавлящеа бобой сужение f на множестве ^ Таотете.4..3. Если графы b=(W,Y) изоморфны Н , то V'^fiV 1р1('0'}=' JCH'O')) , т . е . ооответотвующие друг другу верши­ ны при изомор^шзме имеют одияаноане отепани. Докааатвльотао. DyoTblT^V - произвольная вершина гра^'Э <? 00 отапонью f/Cv)=K . Тогда в & имеетой К взриин, омв:кии I/' . Обозначимa x f j , t / J , , , 5^к . В силу того, ^Tof'V-^W/ явля­ ется изоморфизмом, вершиш f \ • • •, f (1^4) € W" графа Н воа разные и смежнц в е рмн е ^СгГ) , Таким образом, dCkiT)) ^ c/ci)') - Увдтнвая, что - взаимно однозначное отображение, можно дока­ зать, чт:о oiCv)"9- . Из двух последних неравенатв оладуат, что d LV ) - dCHv ) ) . Теошна 4 . 4 . Еоли l-pajii <?=• CV,Y ) ^ Y ) ивомор^яи, то н них одинаково! а ) число вершин и pe^0p(tVi=|v!/i,(>^( «(Y'|)j 6) ЧИСЛО вершак степени К , V* К. ^ О ; в) число яроотнх цик­ лов длиш к,, V к О - 32