Что такое висячие вершины графа
Перейти к содержимому

Что такое висячие вершины графа

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

Графом $G$ называется пара множеств $G = (V, E$, где $V(G)$ — непустое конечное множество элементов, называемых вершинами графа, а $E$ — множество пар элементов из $V$ (необязательно различных), называемых ребрами графа. $E = \<(u , v)\ | u, v \in V\>$ — множество ребер графа $G$, состоящее из пар вершин $(u, v)$. Ребро $(u, v)$ соединяет вершины $u$ и $v$.

Граф — это набор вершин (точек) и соединяющих их отрезков (рёбер).

Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах $N$ — количество вершин, а $M$ — ребер. Количество ребер, исходящее из вершины называют степенью вершины $d(v)$. Для вершины $a$ ребро $(a, b)$ называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).

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

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

Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.

Дерево — это связный неориентированный граф без циклов.

1) У дерева с хотя бы 2 вершинами всегда есть висячая вершина — вершина степени 1.

Действительно, если начать из любой вершины идти по непосещенным ранее вершинам, то в какой-то момент мы прекратим это делать, ведь граф конечный. При этом если из этой вершины не может быть ребер в непосещенные вершины — ведь тогда прекращать рано, и не может быть ребер в посещенные ребра (помимо предыдущей) — ведь тогда есть цикл. А значит, есть ребро только в предыдущую вершину, значит степень равна 1.

2) У дерева с хотя бы 2 вершинами всегда есть две висячие вершины.

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

3) У дерева с $N$ вершинами всегда ровно $N-1$ ребро.

Давайте отрезать от дерева его висячие вершины — при этом число вершин уменьшится на один, число ребер тоже уменьшится на один, а граф останется деревом. Раз граф остается деревом, у него все время будет висячая вершина, пока $N > 1$. В какой-то момент останется только одна вершина и ноль ребер. Раз мы отрезали столько же вершин, сколько ребер, и получили 1 вершину и 0 ребер, значит изначально вершин было ровно на одну больше.

4) Между любыми двумя вершинами в дереве есть ровно один простой путь.

Действительно, если их два, то в графе есть цикл. Быть ноль их не может — ведь граф связный.

5) Дерево — это минимальный по числу рёбер связный граф на $N$ вершинах.

Действительно, если есть связный граф, в котором меньше, чем $N-1$ ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве $N-1$ ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то.

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin

Висячие вершины в теории графов: определение, свойства и примеры решения задач

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

Висячие вершины в теории графов: определение, свойства и примеры решения задач обновлено: 14 ноября, 2023 автором: Научные Статьи.Ру

Помощь в написании работы

Введение

Добро пожаловать на лекцию по Теории графов! В этой статье я буду объяснять вам основные понятия и свойства висячих вершин в графах. Висячие вершины – это одна из важных концепций в теории графов, которая поможет вам лучше понять структуру и связи в графе. Мы рассмотрим определение висячей вершины, ее свойства, а также способы нахождения количества висячих вершин в графе. Кроме того, я приведу несколько примеров решения задач на поиск висячих вершин. Давайте начнем и углубимся в мир Теории графов!

Нужна помощь в написании работы?

Мы — биржа профессиональных авторов (преподавателей и доцентов вузов). Наша система гарантирует сдачу работы к сроку без плагиата. Правки вносим бесплатно.

Определение висячей вершины

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

Визуально, висячая вершина представляет собой “конечную” вершину, которая не связана с другими вершинами, кроме одной.

Свойства висячих вершин

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

Уникальность

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

Конечность

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

Важность

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

Влияние на связность графа

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

В целом, висячие вершины являются важными элементами графа, которые могут влиять на его структуру и связность.

Как найти количество висячих вершин в графе

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

  1. Проанализировать каждую вершину графа.
  2. Для каждой вершины проверить, сколько ребер выходит из нее.
  3. Если количество выходящих ребер равно 0, то данная вершина является висячей.
  4. Подсчитать количество висячих вершин.

Рассмотрим граф с вершинами A, B, C, D и ребрами AB, AC, BD.

Для вершины A количество выходящих ребер равно 2 (AB, AC), поэтому она не является висячей.

Для вершины B количество выходящих ребер равно 1 (BD), поэтому она является висячей.

Для вершины C количество выходящих ребер равно 1 (AC), поэтому она является висячей.

Для вершины D количество выходящих ребер равно 0, поэтому она является висячей.

Таким образом, в данном графе есть 3 висячие вершины (B, C, D).

Таблица свойств висячих вершин

Свойство Описание
Висячая вершина Вершина графа, которая имеет только одну связь с другими вершинами
Степень висячей вершины Количество ребер, связанных с висячей вершиной
Количество висячих вершин в графе Сумма степеней всех висячих вершин в графе
Пример задачи на поиск висячих вершин Дан граф с вершинами и ребрами. Найти все висячие вершины в графе

Заключение

Висячая вершина в графе – это вершина, которая имеет только одну связь с другими вершинами. Она не соединена ни с одной другой вершиной, кроме одной. Висячие вершины могут быть полезны при анализе графов и решении задач, так как они представляют собой конечные точки или “листья” графа. Количество висячих вершин в графе можно найти, подсчитав вершины, у которых степень равна 1. Понимание висячих вершин и их свойств поможет вам лучше понять и анализировать графы в теории графов.

Висячие вершины в теории графов: определение, свойства и примеры решения задач обновлено: 14 ноября, 2023 автором: Научные Статьи.Ру

Средняя оценка 0 / 5. Количество оценок: 0

Поставьте вашу оценку

Сожалеем, что вы поставили низкую оценку!

Позвольте нам стать лучше!

Расскажите, как нам стать лучше?

Укладка графа с планарными компонентами вершинной двусвязности

Пусть графы [math]G_1[/math] и [math]G_2[/math] планарны. Граф [math]G[/math] получается из [math]G_1[/math] и [math]G_2[/math] совмещением вершин [math]v_1 \in G_1[/math] и [math]v_2 \in G_2[/math] . Тогда [math]G[/math] планарен.

Предварительно заметим, что в доказательстве используются утверждения леммы I и леммы II из статьи Укладка графа с планарными компонентами реберной двусвязности. Итак, уложим [math]G_2[/math] на сфере и уложим [math]G_1[/math] на плоскости так, чтобы ребро [math]e_1 \in G_1[/math] смежное с [math]v_1[/math] (если таковое имеется) оказалось на границе внешней грани (по лемме II это возможно). Если такого ребра [math]e_1[/math] не существует, значит вершина [math]v_1[/math] изолирована, в таком случае возьмем любую укладку [math]G_1[/math] на плоскости и переместим точку, соответствующую [math]v_1[/math] во внешнюю грань. Иначе сожмем часть плоскости, содержащую укладку [math]G_1[/math] так, чтобы она вмещалась в одну из граней укладки [math]G_2[/math] смежную с [math]v_1[/math] . Рассмотрим множество [math]U[/math] вершин смежных с [math]v_1[/math] . Уберем кривые, соответствующие ребрам, инцидентным [math]v_1[/math] . Ясно, что после этого множество вершин [math]U[/math] лежит на внешней границе укладки [math]G_1[/math] . Соединим теперь каждую вершину из [math]U[/math] c [math]v_2[/math] непересекающимися жордановыми линиями так, чтобы они не задевали укладок [math]G_1[/math] и [math]G_2[/math] (рис. 1). Таким образом мы совместили вершины [math]v_1[/math] и [math]v_2[/math] в вершине [math]v_2[/math] , а значит получили укладку графа [math]G[/math] на сфере, следовательно [math]G[/math] — планарен.

Докажем утверждение теоремы для одной из компоненты связности графа [math]G[/math] . Ясно, что имея укладки на плоскости каждой из компонент связности графа, мы можем получить укладку на плоскости и всего графа. Итак пусть граф [math]G[/math] связен. Если [math]G = K_1[/math] , то [math]G[/math] очевидно планерен, поэтому предположим, что [math]|EG| \geqslant 1[/math] , а значит имеется по-крайней мере один блок в [math]G[/math] . Рассмотрим связный подграф [math]T[/math] графа блоков и точек сочленений графа [math]G[/math] такой, что [math]\forall v[/math] — т.с. [math]G[/math] имеем [math]\deg(v) \geqslant 2[/math] . Из леммы и из связности [math]T[/math] получаем, что [math]T[/math] — двудольное дерево.

Докажем индукцией по числу вершин в графе [math]T[/math] , что подграф [math]G'[/math] графа [math]G[/math] состоящий из блоков графа [math]G[/math] принадлежащих графу [math]T[/math] планарен (далее будем говорить, что [math]G'[/math] соответствует [math]T[/math] ).

База индукции.

Если [math]|VT| = 1[/math] , то граф [math]T[/math] тривиальный. Его единственная вершина — это блок графа [math]G[/math] , который по утверждению теоремы планарен.

Индукционный переход.

Пусть утверждение верно для [math]|VT| \lt m[/math] . Рассмотрим [math]T[/math] , для которого [math]|VT| = m \gt 1[/math] , и соответствующий [math]T[/math] подграф [math]G'[/math] графа [math]G[/math] . Докажем, что [math]G'[/math] планарен.

Положим [math]G_1[/math] — это блок графа [math]G'[/math] являющийся висячей вершиной дерева [math]T[/math] (вспомним, что в дереве, в котором более одной вершины, всегда есть есть висячие вершины, и то, что висячими вершинами в графе блоков и т.с. не могут быть т.с.), a [math]v[/math] — т.с. в [math]G'[/math] смежная с [math]G_1[/math] в [math]T[/math] . [math]G_1[/math] планарен по утверждению теоремы, т.к. блоки графа [math]G'[/math] совпадают с блоками графа [math]G[/math] . Заметим, что [math]\deg(v) \gt 1[/math] , т.к. [math]v[/math] — т.с., следовательно не висячая. Рассмотрим два случая:

    [math]\deg(v) = 2[/math] в [math]T[/math] (рис. 2). Обозначим за [math]T'[/math] [math]T\backslash \[/math] . Поскольку степень ни одной из т.с. [math]G'[/math] принадлежащих [math]T[/math] (кроме удаленной [math]v[/math] ) не уменьшилась, значит [math]T'[/math] удовлетворяет условиям на [math]T[/math] из предположения индукции. Заметим, что [math]VT’ = VT — 2 = m — 2 \lt m[/math] . Заметим также, что [math]T'[/math] связен, т.к. [math]u[/math] и [math]v[/math] по очереди были висячими вершинами [math]T[/math] и [math]T\backslash \[/math] .

Что такое висячие вершины графа

Задание 6.1. Нарисуйте граф с семью вершинами и шестью ребрами, не имеющий ни одного цикла.
Задание 6.2. Нарисуйте связный граф с семью вершинами и шестью ребрами.
Задание 6.3. Нарисуйте граф с семью вершинами, в котором для любых двух вершин существует один и только один связывающий их путь.
Все предлагаемые решения выносим на доску, обсуждая каждый предложенный ребятами вариант.
Рассмотрим внимательно рисунки, которые строили при ре­шении этих заданий. Что характерно для всех построенных графов? Во-первых, они связные; во-вторых, они не содержат цик­лов. Такие графы выделяются в отдельный класс, представители которого именуются деревьями.

Рис 36
Деревом называется всякий связный граф, не имеющий циклов (рис. 36).
Будем считать, что граф, состоящий из одной изолирован­ной вершины, тоже является деревом.
Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке 36 висячие вершины выделенызакрашенными кружками).

Рис. 37
Лесом называется несвязный граф, представляющий объединение деревьев (рис. 37).
Задача 6.1.
В парке «Лотос» невозможно найти такой маршрут для прогулок по
его дорожкам, который начинается и оканчивается в одной и той же точке и каждую дорожку парка содержит не более раза. Докажите, что некоторые дорожки парка приводят в тупик.
Решение.
Построим граф G, в котором вершины соответствуют перекресткам и тупикам парка, а ребра — его дорожкам.
По условию задачи в графе Gнет циклов, и он является деревом. Существование тупиков в парке эквивалентно существованию висячих вершин в построенном дереве.
Предложение 2. В любом дереве есть висячая вершина. Предположим противное. Рассмотрим произвольную вершину v1 и перейдем из нее по любому ребру в вершину v2. Поскольку степень вершины v2не меньше двух, то из нее по новому ребру можно перейти в вершину v3 и так далее. Но число вершин в графе G конечно. Поэтому, в конце концов, мы приедем в одну из тех вершин, в которых были раньше (см. рис. 38).

Рис. 38
Это означает существование цикла в дереве G, что противоречит условию. Следовательно, в графе есть висячая вершина. Эта вершина будет соответствовать тупику в парке.
Задача 6.2.
Администрация парка «Лотос» (см. предыдущую задачу) решила про­
вести реконструкцию освещения парка. По новому проекту каждый
перекресток и тупик, должен будет освещаться четырьмя светильника­ми, а аллея, соединяющая два перекрестка или перекресток и тупик – шестью. Сколько светильников будет установлено, если в парке 18 перекрестков и тупиков.
Решение.
В предыдущей задаче мы установили, что граф G, описываю­щий перекрестки, тупики и аллеи парка «Лотос» является деревом. Най­дем соотношение между числом вершин и ребер любого дерева. Каждое дерево имеет висячую вершину (см. предыдущую задачу). Удалим вися­чую вершину v0 из дерева Gвместе с ребром, выходящим из этой вер­шины. Полученный граф G1 будет связным, и в нем будут отсутствовать циклы, т.е. граф G1 – также дерево. Из графа G1, найдя и затем удалив висячую вершину v1 вместе с выходящим из нее ребром, можно получить дерево G2 и так далее. Выполнив такие операции, мы получим последо­вательность деревьев, которая оканчивается деревом, состоящим из од­ной вершины и не имеющим ребер. Для этого дерена выполняется соот­ношение: m = n – 1, где n – число вершин графа, а m – число его ребер. Теперь будем добавлять в обратном порядке ранее удаленные вершины и ребра. При каждом возвращении добавляется одна вершина и одно ребро, и для каждого получающегося графа соотношение m = n – 1 будет выпол­няться. Следовательно, мы доказали теорему 9: в любом дереве число ребер на единицу меньше числа вершин.

Поскольку в парке 18 перекрестков и тупиков, то дерево Gбудет иметь 18 вершин и 17 ребер. В парке необходимо установить 18*4 + 17*6 = 174 светильника.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *