Регулярный граф - степень
Cтраница 1
 |
Кубические графы с 6 вершинами. [1] |
Регулярный граф степени 0 совсем не имеет ребер. Если G - регулярный граф степени 1, то каждая его компонента содержит точно одно ребро; в регулярном графе степени 2 каждая компонента - цикл, и, конечно, обратно. Первые интересные 2) регулярные графы имеют степень 3; такие графы называются кубическими. На рис. 2.11 показаны два регулярных графа с 6 вершинами. [2]
Всякий двусвязный регулярный граф степени 3 может быть разложен на непересекающиеся 1-фактор и 2-фактор. [3]
Конечно, каждый регулярный граф степени 1 есть уже 1-фактор, а каждый регулярный граф степени 2 - это 2-фактор. Если любая компонента регулярного графа G степени 2 является четным простым циклом, то G также 1-факторизуем, поскольку его можно представить в виде суммы двух 1-факторов. [4]
Если G - регулярный граф степени п, то существует разбиение множества его вершин, содержащее не более 1 [ я / 2 ] таких подмножеств, что каждая вершина смежна самое большее с одной отличной от нее вершиной того же подмножества. [5]
Поскольку каждый одноцветный класс ребер, определяемый реберной я-раскраской регулярного графа G степени п, являет: я 1 -фактором графа G, из теоремы 12.12 получаем еще одну эквивалентную форму гипотезы четырех красок. [6]
Конечно, каждый регулярный граф степени 1 есть уже 1-фактор, а каждый регулярный граф степени 2 - это 2-фактор. Если любая компонента регулярного графа G степени 2 является четным простым циклом, то G также 1-факторизуем, поскольку его можно представить в виде суммы двух 1-факторов. [7]
Покажите, что существует двудольный граф G G ( Ki 2) 1 в котором Vi и V3 содержат одинаковое количество вершин, причем G является регулярным графом степени р, содержащим. [8]
 |
Кубические графы с 6 вершинами. [9] |
Регулярный граф степени 0 совсем не имеет ребер. Если G - регулярный граф степени 1, то каждая его компонента содержит точно одно ребро; в регулярном графе степени 2 каждая компонента - цикл, и, конечно, обратно. Первые интересные 2) регулярные графы имеют степень 3; такие графы называются кубическими. На рис. 2.11 показаны два регулярных графа с 6 вершинами. [10]
Конечно, каждый регулярный граф степени 1 есть уже 1-фактор, а каждый регулярный граф степени 2 - это 2-фактор. Если любая компонента регулярного графа G степени 2 является четным простым циклом, то G также 1-факторизуем, поскольку его можно представить в виде суммы двух 1-факторов. [11]
Предположим, что v - вершина степени г в графе G. Если G является регулярным графом степени г, то, естественно, после любого числа r - кликовых вставок получающийся больший граф также будет г-регулярным. [12]
Мы утверждаем, что GI - регулярный граф степени А. G не является Д - регулярным графом. [13]
Разумеется, не для всяких k и I регулярный граф степени k и обхвата I вообще существует, но если он существует, то число п - / ( k, l) однозначно определено. [14]
В своем доказательстве целочисленного случая Кениг вновь рассматривает соответствующий двудольный граф и приходит к выводу, что матрица является дважды стохастической тогда и только тогда, когда этот двудольный граф регулярный. В своих двух работах 1916 г. Кениг доказал также, что каждый двудольный регулярный граф степени k является объединением k непересекающихся совершенных паросочетаний. Легко заметить - но эти результаты строго доказаны - что любая дважды стохастическая матрица с неотрицательными элементами должна быть выпуклой суммой матриц подстановок. Изложенный в этих терминах данный результат независимо переоткрыли спустя сорок лет Биркгоф ( 1946) и фон Нейман ( 1953), и теперь он известен как теорема Биркгофа - фон Неймана. [15]
Страницы: 1 2