Вершины дерева имеющие степень 1

Графы: Нужна помощь в объяснении решения задачи на определение степеней вершин.

Пожалуйста, используйте IE6/7/8 с плагином MathPlayer, Firefox с установленными математическими шрифтами или Opera 9.5 и выше.

Здравствуйте. Читаю книгу по дискретной математике и столкнулся с задачей, решение которой не понимаю.
Почему в решении сказано, что количество вершин со степенью 1 равно пяти?

Я построил визуально граф (цифры на рисунке внутри вершин означает их степень)
http://xmages.net/upload/dd618a17.gif
и у меня количество вершин другое — 11 штук (закрашены белым цветом).

Сама задача и её решение ниже.

Задача
Известно, что дерево T имеет три вершины степени 3 и четыре вершины степени 2. Остальные вершины дерева имеют степень 1. Сколько вершин степени 1 есть у дерева Т? (Указание: обозначьте число вершин дерева Т через n и примените лемму об эстафете).

Лемма об эстафете
Сумма степеней всех вершин простого графа G совпадает c удвоенным числом его рёбер.

Решение задачи
Пусть n — общее число вершин нашего дерева. Тогда сумма их степеней равна

3 + 3 + 3 + 2 + 2 + 2 + 2 + (n — 7) = n + 10.

C другой стороны, число ребер дерева Т должно быть ровно на единицу меньше числа вершин, т.е. число ребер равно n — 1. Опираясь на лемму об эстафете, получаем соотношение:

Следовательно, n = 12, откуда вытекает, что число вершин дерева Т со степенью 1 равно пяти.

Редактировалось 1 раз(а). Последний 10.02.2010 14:47.

Источник

Теория Графов 4

Деревья Листья, внутренние вершины Вершины дерева, имеющие степень, равную 1 называются листьями Внутренние вершины дерева вершины, не являющиеся листьями.

Деревья Листья, внутренние вершины Замечание 1 Если в дереве выделен некоторый корень, то дерево называется корневым . В корневом дереве, даже если степень корня равна 1 , он не считается листом. Расин О.В. Деревья

Деревья Листья, внутренние вершины Замечание 1 Если в дереве выделен некоторый корень, то дерево называется корневым . В корневом дереве, даже если степень корня равна 1 , он не считается листом. Расин О.В. Деревья

Деревья Свойства внутренних вершин и реб¼р Предложение 1.1 В любом дереве 1) все внутренние вершины и только они являются точками сочленения. Расин О.В. Деревья

Деревья Свойства внутренних вершин и реб¼р Предложение 1.1 В любом дереве 1) все внутренние вершины и только они являются точками сочленения. 2) каждое ребро является мостом. Расин О.В. Деревья

Деревья Свойства внутренних вершин и реб¼р Предложение 1.1 В любом дереве 1) все внутренние вершины и только они являются точками сочленения. 2) каждое ребро является мостом. Доказательство тривиально и приводится не будет Расин О.В. Деревья

Деревья Свойства внутренних вершин и реб¼р Предложение 1.1 В любом дереве 1) все внутренние вершины и только они являются точками сочленения. 2) каждое ребро является мостом. Доказательство тривиально и приводится не будет Замечание 2 Чтобы предотвратить возможную путаницу для корневых деревьев заметим, Расин О.В. Деревья

Деревья Свойства внутренних вершин и реб¼р Предложение 1.1 В любом дереве 1) все внутренние вершины и только они являются точками сочленения. 2) каждое ребро является мостом. Доказательство тривиально и приводится не будет Замечание 2 Чтобы предотвратить возможную путаницу для корневых деревьев заметим, что корень является точкой сочленения тогда и только тогда, когда его степень больше 1 . Расин О.В. Деревья

Деревья Свойства внутренних вершин и реб¼р Предложение 1.1 В любом дереве 1) все внутренние вершины и только они являются точками сочленения. 2) каждое ребро является мостом. Доказательство тривиально и приводится не будет Замечание 2 Чтобы предотвратить возможную путаницу для корневых деревьев заметим, что корень является точкой сочленения тогда и только тогда, когда его степень больше 1 . Расин О.В. Деревья

Источник

Характеристики графа

Граф называется полным, если любые две различные вершины соединены одним и только одним ребром. В полном графе каждая вершина принадлежит одному и тому же числу ребер, так как она соединена со всеми остальными вершинами. Для задания полного графа достаточно знать число его вершин. Граф, являющийся неполным, можно преобразовать в полный граф с теми же вершинами, добавив недостающие ребра. Дополнением графа называется граф с теми же вершинами, что и граф , и теми ребрами, которые необходимо добавить к графу , чтобы получился полный граф.

Степенью вершины x_i графа называется число d_i , равное количеству ребер графа, инцидентных этой вершине. Вершина называется четной (нечетной), если ее степень — четное (нечетное) число.

Теорема 1. Если конечный граф (без петель) имеет
n вершин и m ребер, то

Теорема 2. Число нечетных вершин любого графа четно.

Теорема 3. Во всяком графе с n вершинами ( n >2) всегда найдутся, по меньшей мере, две вершины с одинаковыми степенями.

Теорема 4. Если в графе с n вершинами ( n >2) в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени n — 1.

Путь и ци кл в гр афе

Путем от x_i до x_j называется такая последовательность ребер графа, ведущая от x_i к x_j , в которой два соседних ребра имеют общую вершину и никакое ребро не встречается дважды. Длиной пути называется число ребер этого пути. Путь от x_i до x_j называется простым, если он не проходит через одну вершину более одного раза.

Циклом называется путь, в котором начальная и конечная вершины совпадают. Длиной цикла называется число ребер в этом цикле. Цикл называется простым, если он не проходит через одну вершину более одного раза.

Теорема 5. Если у графа все простые циклы четной длины, то граф не имеет ни одного цикла нечетной длины.

Связность графа, деревья

Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах, и несвязными в противном случае. Граф называется связным, если любые две его вершины связны, и несвязным в противном случае.

Теорема 6. Связный граф представляет собой простой цикл тогда и только тогда, когда каждая его вершина имеет степень 2.

Ребро ( x_i , x_j ) называется мостом, если в графе , полученном после удаления ребра ( x_i , x_j ), вершины x_i и x_j несвязны.

Связный граф без циклов называется деревом. Вершина дерева, имеющая степень 1, называется висячей.

Плоские графы

Граф называется плоским, если его можно изобразить на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины. Чертеж графа, на котором никакие два ребра не пересекаются, называют плоским представлением графа.

Плоское представление имеет только плоский граф, и обратно: у всякого плоского графа всегда найдется плоское представление.

Гранью в плоском представлении графа наз ывают часть плоскости, ограниченную простым циклом и не содержащую внутри других циклов. Часть плоскости, расположенная вне плоского представления графа и ограниченная изнутри простым циклом, называется бесконечной гранью. Две грани называются соседними, если их границы имеют хотя бы одно общее ребро. Мост, соединяющий два цикла, называется перегородкой.

В плоском представлении дерева за грань принимают всю плоскость чертежа.

Для всякого плоского графа без перегородок число вершин n , число ребер m и число граней с учетом бесконечной g связаны соотношением

n — m + g = 2,

которое называется формулой Эйлера.

Плоский граф н азывается максимально плоским, или триангулированным , если к нему невозможно добавить ни одного ребра так, чтобы полученный граф был плоским.

Операция добавления новых ребер, в результате которой в плоском представлении графа каждая грань имеет ровно три вершины, называется триангуляцией графа.

Теорема 7. Для любого плоского графа с уществует плоское представление, в котором все ребра — прямолинейные отрезки.

Эйлеровы графы

Эйлеровым путем в графе называют путь, содержащий все ребра графа и проходящий через каждое по одному разу. Эйлеровым циклом в графе называют цикл, содержащий все ребра графа и проходящий через каждое по одному разу. Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

Теорема 8. Эйлеров граф является связным, и все его вершины — четными.

Теорема 9. Если граф связный и все его вершины четны, то он обладает эйлеровым циклом.

Теорема 10. Если граф обладает эйлеровым путем с концами А и В, то граф связн ый и А и В его единственные нечетные вершины.

Теорема 11. Если граф связный и А и В его единственные нечетные вершины, то граф обладает эйлеровым путем с концами А и В.

Теорема 12. Если граф связный, то можно построить цикличный маршрут, содержащий в се ребра в точности два раза, по одному в каждом направлении.

Гамильтоновы графы

Гамильтоновым путем в графе называют путь, проходящий через каждую вершину графа в точности по одному разу. Гамильтоновым циклом в графе называют цикл, проходящий через каждую вершину графа в точности по одному разу. Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.

Теорема 13. Граф с m вершинами имеет гамильтонов цикл, если для любой его вершины A_i

степ. ( A_i ) ³ m /2.

Ориентированные графы

Ребро графа называется ориентированным, или дугой, если одну вершину считают началом, а вторую концом ребра. На рисунке дугу изображают стрелкой. Дугу с началом в вершине x_i и концом в вершине x_j обозначают ( x_i , x_j ).

Граф, все ребра которого ориентированы, называется ориентированным графом. Число дуг, исходящих из вершины ориентированного графа x_i , называется полустепенью исхода вершины x_i ; число дуг, входящих в вершину x_i , называется полустепенью захода вершины x_i .

Вершина x_i называется источником, если ее полустепень захода равна нулю; вершина x_i , называется стоком, если ее полустепень исхода равна нулю.

Последовательность дуг ( x ₁ , x ₂ ), ( x ₂ , x ₃ ) … ( x_{k -1} , x_k ), в которой конец предыдущей дуги совпадает с началом следующей, называется маршрутом от x ₁ до x_k . Маршрут, в котором первая и последняя вершины совпадают, называется замкнутым. Маршрут, в котором все вершины различны, называется путем от x ₁ до x_k .

Если существует путь из вершины x_i в вершину x_j , то говорят, что x_j достижима из x_i . Замкнутый путь называется контуром.

Полным ориентированным графом называется граф , в котором каждая пара вершин соединена в точности одной дугой.

Теорема 14. Всякий полный ориентированный граф имеет путь, проходящий через все вершины.

Ориентированный граф можно задать с помощью матрицы инцидентности. Пусть x ₁ , x ₂ , …, x_n — вершины графа, ℓ₁, ℓ₂, …, ℓ _m — дуги графа.

Матрицей инцидентности графа называется матрица В _{n ´ m} , у которой элемент b_ij равен 1, если дуга ℓ _j исходит из вершины x_i , равен , если дуга ℓ _j входит в вершину x_i , равен 0, если дуга ℓ _j и вершина x_i не инцидентны.

Источник