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

Пусть Г'. V V отображение йз V в V" , Тогда множдотво (if,1(7); является подо.!кок0отвом V . т . е . би­ нарным отношенкэм на V . Отсюда оледует, что отображения можно считать частным случаем бинарных отношений. ГЛАВА Й. ОСНОВНЫЕ ПОГМТШ ТЕ ВШ ГРАФОВ ^2.1. rpaiTiH. LfarbTHrtiafTibt. Поендотоа'^ы Графом называется пара ( ? = ( V , X') , где V - конечное на-- пус -е мнояеотво, называеиоа вдожаствсм вершш графа, а д - ко­ нечное множество неупорядоченных пар различных элементов из V , иаэ1' земое множеотвом ребер графа. Элементы шожвотва V лазы- ьаютсл вершинаш (или уалаш) графа, а элементы множества X - его ребрами. Иногда и .ог.еотва верпин и ребер графа G обозначают V((r) aX (ir) . Еоли мнояеотЁО ребер У(<г) , графа щахо()((^)'Ю' то граф (? называется луотшл гтзафой или нуль-rpaiiом, ,,з приведен­ ного определения след1'ет, что каждое робро ^'рафа ^ яаляетоя двухэлементным поданожвотвом множества вершки V((?) . Если па­ ра X^ i i Tf iCr } . , где V, , яв-тается ребром графа & , т . а . х ё Х , то вершины и называю-^"я омежшш, а ребро CG и каадая из вершнн V viV- - ияцидантншли. В этом случае говорят, что ребро (С соединяет -вершины V и ЬТ, , в ^ v. ИТ называ- югоя концами ребра X . Два ребра X назнваютоя смежными, золл они тщйдентны од!!ой н той жа вершине. Таким образом, верши- нн t'" и/г?" оыбжны, если оутеотвует увбро 3 . 6 X таксе, что X ; два ребра )( смежны, если Смежность вертян ^ ,1^" и ребер JC будем обозначать так: и Сйсл ^ . Из приввдв"тшх определений олелует, что « графах любые дав различные вершины могут быть ооеданены не оолее чем одним ребром. Такие графы называют иногда простыми графами. Графы удобно прс этавлять виде диаграмм, состоящих йз,то­ чек, изоброжагадих вершиш граф , и линий, соединяющих иакото^)Ы0 пары точек, которые изображают ребра графа. Например, на рис,2.1 изобраяен граф G=L ^ , X ) , для которого V=lVl. «ri, iT^i ; где } ; X ) Н € , X e ' К < 5 ! ; a : ^ 4 « в , { . в атом графе смажнымя яв.чяютоя, в частности, вершины 'tf( и и ребра и Л\ . Вершина Vi и ребро ЗС^ ~ инцидентны. е