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

Лдм.','а ЗЛО. Любой контур орграфа содержит элемонтарный icoHTyp. -53.Э. Связнооть. Комяонентн Граф G-(VjX) называется овязшм, если дая люйых двух вер­ шин £ V графа существует простая цапь, ооэдиняющая эти вершиш Э — проотая {'V- уУ' )-Ц 0 П Ь . Каждая впршйиа связана оама о - йой. Из результатов §3.1 следует, что в данном определешл! т ер - WH "проотая цппь" может быть заменен термином "маршрут". Обра­ щаем внимание нй порядок следования кванторов. Из овяэности не с.10дуот оущестпования простой цапи, содержащей вое варшнн. Но справедлива оледущая теорема. Таопема 3 . 1 . х'раф S -01^ X ) связный тогда м только тогда, когда сувдвстауе'г маршрут, оодерквщий (проход«'-пяй "'spes) вое ввршии! G . Наобхолчмоотъ С =») . Перенумеруем вое вершины графа] J г'р } . Из онязнооти <? олад- чт, что \/L=-l,f-i 3 • тоотая "tTc+i) - цепь. Обозначим эти простые C t f c - I ^ c t i ) цепи Ч№03 . Тогда оце1а..а всех этих простых цаяей является маршрутом, содержащим все вершиш графа, Доотаточнооть ( . Если существует маршрут уЧ , содер­ жащий Ейе вершины графа, то лг ''хв две вершины vr графа ^ M0I7T быть соэдннены соответствующим цодмартрутом '(простой ^ е - пыо) маршрута уИ ; Кошснеитой свпзноо'Сй графа Q (иди просто компс эитой) называется максимальный 0Б.,4ний подграф этого графа. Maк^. шаль- нсоть компоненты пояймаегся в смысле отношения включения, т , а . если Gi - кошонента гра^а 6- , то любой надараф Н графа $ч ( И (?ч ) либо йвляетоя несвязным , либо Н <^6^ . Очбт дно, граф (? связный тогда и только тогда, когда имеет единотвенную компоненту, совпадающую о ^ . П а рис.3.3 показан пример графа О- о 12 вершинами, имекщаго 4 компоненты. Рио.3.3