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

ощнно-нвпереоекаюивхоя простых { IT -'Ш' )-цеп0Й, Эга теорема называется также теоремой Менгера в В01шнной форме. Существует результат, полученный Фордом и Фелкврооном, крторий называют теоремой Менгера в ребервой форме. Теорема 3.13. Минимальное чиоло ребер, разделяющих верши­ ны'iT n W , равно на55большему числу реберно-напервсекающихоя ( 4Г- liT )_цеп0й. Из этих теорем слр'^ет результат, характеризующий реберную, овязяооть графа. \ Тоошма 3.14. Граф ^ - К-рвббрно-связ._^й (^ ( ^ ) 5^ (^ ) тог­ да и только тогда, когда V tT, г<А € V оущеотаует хотя бы ,4, рвберно-нвпервоекающахоя )-цепвй. Теореиа Менгера в реберной форле иопольауется, в чаотноо- ти, для решения зьдач о максимальном яотоке в транспортных се­ тях. ГЛАВА 4 . ЙШМОШШ Выше было введено понятие равенства ;..ух графов ( о р г р - ; J O B ) , требующее оовпадвния множеств верши и ребер (дуг) этих графов (орграфов). Тг-ой подход являчтоя чрезмерно жеотким. Дейотвитально, простое изменение обозначений вершин графа дает новый гр«||. Если граф задается диаграммой, то перечерчивание диаграммы также приводит к новоиу графу. Однако во многих слу­ чаях удобно отвлечься от таки второ гепеиных факторов, как раз^шчие в обозначении вершин или различное раоположение Е-р~ шин в диаграмме графа и т.п. 1елательно ввеоти такое понятае тождеотва 1'рафов, которое учитывало бы лишь оамые су,.,40тнвнныв черты грфов, а именцо, тодсдаотво их структур. Таким П0|..'*тием является понятие изоморфизма. §4J . . И.ар.мотхГ)Изм граФов Два графа ^ "=(V,X) и называют изоморфным, ес­ ли оущ0о1'вувг взаимнооднозначное ооответствив , оох- раняющее смежнооть, т , в . отображающее омежше вершины графа ^ в оивжнцв вершвдщ Н и обратно. Воли г р а ^ чН изоморс1,ш, то пишем 6''^Н . Отображение S . уотанавливающее. изоморф- нооть х'рафоа, называетоя иаомсрфизмсм. Если нужно указать яв­ но, какое отображение является изомор*1а8мом, пи1вут б Н • Дяннсэ определение изоморфизма в оимаоличеокой форме можно аа- пноать Так; 30