Регулярный граф - степень
Cтраница 2
 |
Кубические графы с 6 вершинами. [16] |
Регулярный граф степени 0 совсем не имеет ребер. Если G - регулярный граф степени 1, то каждая его компонента содержит точно одно ребро; в регулярном графе степени 2 каждая компонента - цикл, и, конечно, обратно. Первые интересные 2) регулярные графы имеют степень 3; такие графы называются кубическими. На рис. 2.11 показаны два регулярных графа с 6 вершинами. [17]
Пусть G ( V, H) - конечный граф, не содержащий петель, где V и Я - множества его вершин и ребер соответственно. Цепь, соединяющая вершину и с вершиной v, называется ( u - v) - цепью. Регулярный граф степени г называется г-регулярным. Числа реберной и вершинной связности обозначаются через K ( G) и x ( G) соответственно. Если K ( G) k ( где k - целое положительное число), то граф G называется k - реберно-связ-ным. [18]
Пусть G - укладка планарного графа, все компоненты связности которого 3-связны. Обозначим через G граф, полученный из G с помощью замены каждой вершины степени d 3 на d - угольник. Поскольку G - регулярный граф степени 3, то дуги е и е2 должны быть различимыми. Ясно, что в G существует соответствующий путь. [19]
Соединим ребрами те и только те пары из одной светлой и одной темной точки, для которых в пересечении соответствующей строки и соответствующего столбца содержится знак инцидентности. Мы, очевидно, получим регулярный граф степени q 1, состоящий из 2 ( q2 q 1) точек. Каждое ребро этого графа соединяет одну светлую и одну темную точку, поэтому граф является бихроматическим. Ясно, что никакой его цикл не может состоять из нечетного числа ребер. Следовательно, длина кратчайшего цикла должна быть не меньше шести. Но по аксиоме 13 плоскость обладает собственным треугольником, которому на графе соответствует цикл из шести ребер. [20]
Ps j и Ps, Ps и В соединены ребрами. Граф называется связным, если для любых его двух точек существует соединяющий их маршрут. Число ребер, составляющих маршрут, называется длиной маршрута. Маршрут, соединяющий точку с самой этой точкой, называется циклом. Кратчайший цикл графа на рис. 91 состоит из пяти ребер, а самый длинный - из девяти ребер. Наш пример на рис. 91 представляет собой регулярный граф степени три. Длина кратчайшего цикла графа называется обхватом графа. Цикл, проходящий через каждую точку графа, называется гамильтоновой цепью, а граф с такой цепью - графом Гамильтона. [21]
Страницы: 1 2