Граф G —
это совокупность двух конечных
множеств: множества точек, которые
называются вершинами, и
множества пар вершин, которые
называютсяребрами. На
рис. 10.4.1 изображен граф, имеющий, пять
вершин и шесть ребер. Если
рассматривается множество
упорядоченных пар точек, т.е. на
каждом ребре
задается
направление, то
граф G называется ориентированным.
В противном
случае G
называется неориентированным
графом.
Ребра,
имеющие одинаковые концевые вершины,
называются параллельными. Ребро,
концевые вершины которого совпадают,
называется петлей. На
рис. 10.4.1 а4 и а5 — параллельные
ребра, a а6 —
петля.
Вершина
и ребро называются инцидентными друг
другу, если вершина является для
этого ребра концевой точкой. На рис.
10.4.1 вершина Р3 и
ребро а3инцидентны
друг другу.
Две
вершины, являющиеся концевыми для
некоторого ребра, называются смежными
вершинами. Два
ребра, инцидентные одной и той же
вершине, называются смежными
ребрами. На
рис. 10.4.1 Р1 , Р2 — смежные
вершины, а а1,
а4 —
смежные ребра.
Степенью
вершины называется
число ребер, инцидентных ей. Вершина
степени 1 называется висячей. Вершина
степени 0 называется изолированной. На
рис. 10.4.1 степень вершины Р1 равна
трем, Р4 —висячая
вершина, Р5 —изолированная.
Теорема
1. В
графе G сумма
степеней всех его вершин — число
четное, равное удвоенному числу
ребер графа:
Теорема
2. Число
нечетных вершин любого графа, т.е.
вершин, имеющих нечетную степень,
четно.
Граф G называется полным, если
любые две его различные вершины
соединены ребром и'он не содержит
параллельных ребер.
Дополнением
графа G называется
граф с теми
же вершинами, что и граф G, и
содержащий, только те ребра, которые
нужно добавить к графу G, чтобы
получился полный граф. На рис. 10.4.2
изображены следующие графы:
G1 —
полный граф с пятью вершинами, G2 —
некоторый граф, имеющий пять
вершин, 2 — дополнение
граф G2.
Путем в
графе называется такая последовательность
ребер, ведущая от некоторой начальной
вершины Р1 в
конечную вершину Рn,
в которой каждые два соседних ребра
имеют общую вершину и никакое ребро
не встречается более одного раза.
Например, в графе, изображенном на
рис. 10.4.1, последовательность
ребер (а1,
а2, а3, а4, а5, а6) образует
путь, ведущий от вершины Р1 к
вершине Р4.
Циклом называется
путь, начальная и конечная вершины
которого совпадают. На рис. 10.4.1 ребра
(a1,
a3,
a4)
образуют цикл.
Цикл
графа G называется простым, если
он не проходит ни через одну
вершину G более
одного раза. Длиной
пути или
цикла называется число ребер этого
пути или цикла. |