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

омБжяцхЧГ . Очевндпо .ГС''") явшег-оя Г'азд0.1шющр:м миожоотлом. Та­ ким образом , по определению Х(<г) imeaw:Vv6V Iffor,) j , Отсюда оладуат, ^ ^ . По для простого графа ir(v)l-<:/^'U") . Поэтому • Таорема З.Г . для любого авязного (fpv^) -графа X ( f ) >где - це^шя чаоть числа С , Доказатальство. Так как , то т . е . S'(G-)-^[^f/p 1 . Отсюда и из теоремы 3.7 получаем утвврадепйе -З.В Разрезом графа называется .янгамальное (по лметегдаю) гяюжество ребер, удвлениа которых увелташавт число компонент графа. ^ Реберной связностью ^('^)графа &• называется шшималыюе , чиоло ребер, удалвшю котс^нх np,.jo-^iT к неовязноглу или триви­ альному гра{|!у, т . е . Cf) - ьшимальное число робер по всем разрезам гра,фа. Очевидно, если (? - неовязный, то Ж'(<у) - О] если имеет мост, то = ^ Граф б называется К -ребарно-овязным, если Ж. ( 5 - ) ^К, т . е . воли для того, чтобы сделать его нвовязшил, нужно удалить не, менее К ребер. Taic как ребра, ипцадентша одной вершине, образуют разрез, то Приведем баз доказатвльотаа два теоремы, характеркзуюдав величину Cfr). . . I с Теотема -3.9 ; (Уитни). Для любого rpatja ^ с ) ^ f ^ и (^)• Теорема 3.,Г0. Пусть (г -граф с Р вершинайи; Тогда, аоли Ш ) > ^ C P A J ' . т с Теорема З^И.Длн любых цетах чисел v SC ) оущеотвует граф 0-, , у которого a i 9 ) ~ C . ' 53.7. Теорема Менгата Теорема Мепгера- ктассический результат теории графов, связывающий связность графа с числом вераинно-непвресвкающихоя, цепей между двумя вершинами. Пусть тГ ,1 ^ - две вернины связного графа G •. Две простые )-двпи называются вар !Ш1нно ~непвр0овкающи1тоя, воли ие имеют общих вершин, Кроме 1/" , и раберно-нвпераовкаюпг.гшоя, если у них н0_т_общих ребер. ' Теорема 3.12, (Менгар). ?>1иш1Мально0 число, ввуши, разделяв­ ших дае. йеомежннв .вершины С иW , равно наибольшему числу 'вер- '