Спирина, М.С. Дискретная математика

Рис. 2.2. Дополнение Gs графа G5 до графа G2, изображенного на рис. 2.1, б Рис. 2.3. Ориентированный граф случаем этого свойства будет следующее правило: дополнением полного графа будет нуль-граф, и наоборот. Если все пары ( Vh Vt) во множестве X являются упорядочен­ ными, т.е. кортежами длины 2, то граф называется ориентирован­ ным, орграфом, или направленным. Поскольку сразу может быть не известно о каком графе идет речь, в этой главе мы будем употреб­ лять круглые скобки для обозначения ребра вместо угловых, как это должно было быть для кортежей. В них будет помещаться соот­ ветствующая пара вершин. В таком случае ребра принято изобра­ жать стрелками (рис. 2.3). Началом ребра называется вершина, ука­ занная в кортеже первой, концом — вторая вершина этой пары (графически она указана стрелкой). Ребра ориентированного гра­ фа имеют определенные фиксированные начало и конец и назы­ ваются дугами. Очевидно, дуги (Pi, V3) и ( F3, Fj), если они обе существуют, различны: (Vh V3) ф ( V3, F,). Степенью вершины ориентированного графа называ­ ется число ребер, для которых эта вершина является концом . началом Степень входа вершины V будем обозначать deg+( Р), а степень вы­ хода — deg_(F). На рис. 2.3 deg+(F,) = 1, deg+(K2) = 1, deg+(K3) = = 2, deg_( К,) = 1, deg_( V2) = 2, deg.( P3)= 1. Дуги орграфа называются кратными, если они имеют одинако­ вые начальные и конечные вершины, т.е. одинаковые направле­ ния. Например, кратны дуги м(Р2, У3) и t(V2, V3) на рис. 2.3. Последовательность попарно инцидентных вершин Vh, Vh, ..., Vik неориентированного графа, т. е. последовательность ребер не­ ориентированного графа, в которой вторая вершина предыдуще­ го ребра совпадает с первой вершиной следующего, называется маршрутом. Число ребер маршрута называется длиной маршрута. Например, на рис. 2.1, в HCDFD — маршрут длиной 4. Обозначе­ ние: \HCDFD\ = 4. Очевидно, что если Vh, Vh, Vu — маршрут длины к - 1, то и Vit, Vit l, Vh, Vu также будет являться маршру­ 72