Смежные вершины графа это

Смежные вершины графа это

Опр. Две вершины в графе (орграфе) G называются смежными, если существует ребро(дуга), которая их соединяет. Пусть v, w вершины, а e=(v,w) — ребро (дуга) их соединяющая. Тогда вершина v и ребро (дуга) e являются инцидентными, вершина w и ребро (дуга) e также являются инцидентными. Два ребра инцидентные одной вершине называются смежными.

Пример 1.2.1. Рассмотрим неориентированный граф на рис.1.1.1.в).

Вершины 1,2 -смежные, а вершины 2,3 не являются смежными.

Вершина 1 инцидентна ребру (1,2). Ребро (2,3) инцидентно вершине 2.

Вершина 1 не инцидентна ребру (3,2).

Ребра (1,2) и (3,2) смежные, т.к. у них есть общая вершина.

Пример 1.2.2. Рассмотрим ориентированный граф на рис. 1.1.1.в).

Вершины 1,2 -смежные, а вершины 2,3 не являются смежными.

Вершина 1 инцидентна дуге (1,2). Дуга (2,3) инцидентна вершине 2.

Вершина 1 не инцидентна дуге (3,2).

Опр. Степенью вершины v графа G называется число ребер это исходящих из этой вершины (инцидентных v).

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

Опр. Число вершин называетсяпорядком графа.

Существует всего 4 разных графа порядка 3.

Теорема: Сумма степеней вершин графа равна удвоенному числу его ребер.

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

Опр. Вершина называется четной, если в ней сходится четное число ребер, и нечетной, если число всех сходящихся в ней ребер нечетно.

Полустепенью исхода вершины v орграфа G называется число 6 (v) дуг исходящих из вершины v (т.е. v является началом этих дуг).

Полустепенью захода вершины v орграфа G называется число 6 (v) дуг входящих в вершину v (т.е. v является концом этих дуг).

Замечание. В случае неориентированного псевдографа вклад каждой петли при расчете степени инцидентной вершины равен 2.

Пример 1. Рассмотрим ориентированный псевдограф, изображенный на рис.1.1.1.

Пример 2. Рассмотрим неориентированный псевдограф, изображенный на рис.1.1.1.

Маршруты, пути, циклы, связность.

Пусть G=(V,E) граф с p вершинами и q ребрами, т.е.

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

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

1. Две цепи из трех разных ребер:

2. Три разные ребра, из которых нельзя образовать цепь:

Опр.Цепь называется простой, если ее вершины различны, кроме, может быть первой и последней.

Опр. Замкнутая цепь называется циклом. Замкнутая простая цепь называетсяпростым циклом.

х1 x2 х3 х6 х7 — цепь длины 5 (все ребра в ней различны). Эта цепь не является простой, так как при обходе вершину v3 мы посетили два раза.

х6 х7 х8 х3 — цикл.

Опр.Граф без циклов называется ациклическим.

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

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

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

Опр. Подграфом графа G называется граф, у которого все вершины и ребра принадлежат G. Если G1 – подграф графа G, то G называется надграфом графа G1.

Опр. Остовный подграф — это подграф графа, содержащий все его вершины.

Опр.Ребро, после удаления которого граф из связного превращается в несвязный, называетсямостом.

Основные понятия и определения.

Пара (V(G), E(G)) называется простым графом, если V(G) – непустое конечное множество элементов, называемых вершинами (или узлами, или точками), а E(G) – конечное множество неупорядоченных пар различных элементов из V(G), называемых ребрами (или линиями). В простом графе данную пару вершин может соединять не более чем одно ребро.

Между элементами множества вершин и множества ребер определено отношение инцидентности. Говорят, что ребро е инцидентно вершинам v1, v2, если оно соединяет эти вершины и наоборот, каждая из вершин v1, v2 инцидентна ребру е.

Читайте также:  Слова начинающиеся с цифр

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

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

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

Кратностью ребер называют количество одинаковых пар.

пример

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

Две вершины называются смежными, если существует ребро, концами которого они являются. Два ребра называются смежными, если они имеют общую вершину.

Смежные вершины – вершины, инцидентные одной дуге.
Смежные дуги – это дуги инцидентные одной вершине.

Степени вершин и полустепени исхода и захода.

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

Вершина, локальная степень которой равна 0, называется изолированной; степень которой равна 1 – висячей.

Полустепенью исхода (захода) вершины v орграфа D называется число дуг орграфа D, исходящих из вершины v (заходящих в вершину v).

Количество вершин и ребер в графе G обозначим соответственно через n(G) и m(G), а количество вершин и дуг в орграфе D – через n(D) и m(D).

Для любого псевдографа G выполняется равенство

(Cумма степеней всех вершин = удвоенное количество ребер в графе)

Для любого ориентированного псевдографа D выполняется равенство

(Cумма полустепеней исхода и захода всех вершин = количество ребер в графе)

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

Операция подразбиения (измельчения) дуги (u, v) в орграфе D = (V, E) состоит в удалении из Е дуги (u, v), добавлении к V новой вершины w и добавлении к Е | <(u, v)>двух дуг (u, w), (w, v). Аналогично определяется операция подразбиения ребра в графах.

Орграф D1 называется подразбиением орграфа D2, если орграф D1 можно получить из D2 путем последовательного применения операции подразбиения дуг. Аналогично определяется подразбиение графа.

Орграфы D1, D2 называются гомеоморфными, если существуют их подразбиения, являющиеся изоморфными.

Матрицы смежностей и инциденций вершин графов и орграфов.

Матрицей смежности орграфа D называется квадратная матрица A(D)=[aij] порядка n, у которой

Матрицей инцидентности орграфа D называется (nxm) –матрица B(D)=[bij], у которой

Матрицей смежности графа G называется квадратная матрица A(G)=[aij] порядка n, у которой

Матрицей инцидентности графа G называется (nxm) –матрица B(G)=[bij], у которой

Основные свойства матриц смежности:

  1. Матрица смежностей вершин неориентированного графа A (G) является квадратной и симметричной относительно главной диагонали.
  2. Элементами матрицы A (G) являются целые положительные числа и число ноль.
  3. Сумма элементов матрицы A (G) по i-й строке (или по i-му столбцу) равна степени соответствующей вершины δ ( xi ).

Из определения следует, что сумма элементов i-й строки матрицы A (G)орграфа равна полустепени исхода δ+ ( xi ), а по i-му столбцу – полустепени захода δ¯ ( xi ).

Свойства матрицы инцидентности неориентированного графа:

  1. Сумма элементов матрицы на i-й строке равна δ ( xi ).
  2. Сумма элементов матрицы по i-му столбцу равна 2.

Матрица инцидентности орграфа G обладает следующими свойствами:

  1. Сумма строк матрицы B(G) является нулевой строкой.
  2. Любая строка матрицы B(G) является линейной комбинацией остальных строк.
  3. Ранг матрицы B(G) равен p-1.

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

Граф, у которого множество ребер пусто, называется вполне несвязным (или пустым) графом. Вполне несвязный граф обозначают Nn.

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

Граф, у которого все вершины имеют одну и ту же локальную степень n, называется регулярным (или однородным) степени n. Регулярные графы степени 3 называются кубическими (или трехвалентными). Среди регулярных графов особенно интересны так называемые платоновы графы – графы, образованные вершинами и ребрами пяти правильных многогранников — Платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.

Читайте также:  Прога для web камеры

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

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

Граф называется связным, если его нельзя представить в виде объединения двух графов, и несвязным в противном случае.

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

Определение. Связный регулярный граф степени 2 называется циклическим графом.

Смешанный граф — Граф, содержащий как ориентированные, так и неориентированные рёбра

Если х = – ребро графа, то v, w называются концами ребра х, в этом случае говорят, что ребро х соединяет вершины v и w.

Если вершина v является концом ребра х, то говорят, что v и х инцидентны .

Вершины v, w графа G(V,X) называются смежными, если ÎХ.

Два ребра называются смежными, если они имеют общую вершину.

Рассмотрим граф на рисунке 13.1.

Вершины v5, v6 – смежные, т.к. 5, v6>- ребро. Вершины v5, v3 – не смежные, т.к. нет ребра их соединяющего.

Степень вершины v – это количество ребер графа, инцидентных этой вершине. Обозначение d (v).

Заметим, что вклад каждой петли равен двум.

Если степень вершины равна единице, то такая вершина называется висячей.

Если степень вершины равна нулю, то такая вершина называется изолированной.

Значит, вершины v1 и v4 – висячие, а вершина v7 – изолированная.

Теорема о сумме степеней вершин графа: Для любого псевдографа G(V, X) выполняется равенство:

m – количество ребер графа. Действительно, каждое ребро графа инцидентно двум вершинам.

Проверим справедливость теоремы для графа 13.1:

m =7, 7× 2 =14 и 1+2+5+1+2+3+0 =14.

3. Способы задания графов

Один из способов задания графа уже рассмотрен – это геометрическое изображение, т.е. диаграмма.

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

Матрица инцидентности графа.

Матрицей инцидентности графа G(V, X) называется матрица размера m´ n, элементы которой определяются следующим образом:

В любой строке матрицы инцидентности два или один элемент не равны нулю, т.к. каждое ребро соединяет две вершины, а если ребро – петля, то вершину саму с собой.

Матрица инцидентности однозначно определяет структуру графа, что позволяет читать всю необходимую информацию о графе. Например, выявлять изолированные и висячие вершины, петли; определять степени вершин. Информация о ребрах считывается по строкам, о вершинах – по столбцам.

Составим матрицу инцидентности для графа 13.1. Это матрица размера 7´ 7:

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

В третьей строке только один элемент не равен нулю, следовательно третье ребро- петля.

Суммируя элементы по столбцам с учетом того, что вклад петли равен двум, можно определить степень каждой вершины.

Матрицей смежности графа G(V, X) называется квадратная матрица n´ n, элементы которой определяются следующим образом:

k – количество ребер, соединяющих вершины vi и vj .

Составим матрицу смежности для графа 13.1. Это квадратная матрица размера 7´ 7:

Матрица смежности неориентированного графа симметрична относительно главной диагонали.

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

Сумма элементов верхнего или нижнего треугольника вместе с главной диагональю равна количеству ребер в графе. Для нашего графа сумма равна (учитывая только элементы не равные нулю): 1+1+1+2+1+1=7.

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

Читайте также:  При выключении компьютера кулеры продолжают работать

4. Маршруты в неориентированном графе

Определение: Маршрутом , соединяющий вершины v1 и vk+1 , называется последовательность v1x1v2x2…vkxkvk+1 , где k³ 1, vi Î V, xiÎ X, ребро xi соединяет вершины vi с вершиной vi+1 . Вершина v1 (v нач)– начало маршрута (начальная вершина), vk+1 (v кон)– конец маршрута (конечная вершина).

Для графа 13.1 построим маршрут, соединяющий вершину v1 с вершиной v5 :

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

Если в маршруте есть кратные ребра, то в последовательность включают начальную вершину, ребра и конечную вершину. Или пользуются комбинированной записью: в последовательность включают все вершины и только кратные ребра.

Перепишем наш маршрут, использую комбинированную запись: v1v3v3v2v6x7v5 . В последовательность включено только кратное ребро x7 .

Длиной маршрута l называется количество ребер в нем.

В нашем маршруте 5 ребер, значит его длина l =5.

Познакомимся с видами маршрутов.

Если vнач = vкон , то маршрут называется замкнутым.

Если vнач ¹ vкон , то маршрут называется незамкнутым.

Виды незамкнутых маршрутов:

Незамкнутый маршрут, в котором все ребра попарно различны называется цепью.

Цепь, в которой все вершины попарно различны называется простой цепью.

Виды замкнутых маршрутов:

Замкнутый маршрут, в котором все ребра попарно различны называется циклом.

Цикл, в котором все вершины попарно различны называется простым циклом.

Заметим, что петля или кратное ребро являются простыми циклами.

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

5. Операции над графами.

Так как граф G(V, X) задается двумя множествами V и X , то для него определены теоретико-множественные операции : объединение и пересечение.

Кроме этих операций познакомимся с понятиями : подграф и сурграф.

Подграфом графа G(V, X) называется граф G ’ (V ’ , X ’ ) , где G ’ Í G, X’Í X.

Подграф G ’ (V ’ , X ’ ) графа G(V, X) называется собственным, если G ’ Ì G, X’Ì X.

Подграфом графа G(V, X) , порожденным множеством V1 Í V, где V1 ¹Æ, называется граф G1(V1, X1), где Х1 Í Х и соединяет вершины только из V1 .

Сурграфом графа G(V, X) называется граф G”(V, X”), где V=V, X” Ì X.

На рисунке 13.6 представлен собственный подграф графа 13.5.

На рисунке 13.7 – подграф графа 13.5, порожденный множеством V1 =1, v2, v4, v6>.

На рисунке 13.8 – сурграф графа 13.5.

6. Связность. Компоненты связности

Пусть дан псевдограф G(V,X).

Две вершины v и w называются связанными (или вершина v достижима из w), если :

б) существует маршрут, связывающий вершины v и w.

Определенное на множестве V отношение достижимости или связности является бинарным эквивалентным отношением (проверьте самостоятельно). А значит, множество V можно разбить на классы эквивалентности V1 V2 …Vk, где V1 ÈV2È …ÈVk=V и V1 ÇV2 Ç…ÇVk = Æ.

Все вершины, принадлежащие одному подмножеству Vi связанные, а вершины, принадлежащие разным подмножествам – несвязанные.

Каждое подмножество Vi называется компонентой связности графа G(V,X).

Согласно выше сказанному можно сформулировать определение компоненты связности следующим образом:

Компонента связности графа G(V,X) – это связный подграф, не являющийся собственным подграфом никакого другого связного подграфа графа G(V,X).

Количество компонент связности графа G(V,X) обозначается P(G).

На рисунке 13.9 представлен граф, у которого три компоненты связности, т.е. P(G) =3: G1, G2, G3

Введем понятие связного графа.

Граф G(V,X) называется связным, если любые две его вершины достижимы (связанные).

Или: граф G(V,X) называется связным, если P(G) = 1.

Тогда, несвязный граф имеет P(G) >1.

С понятием компонента связности связаны понятия: разделительная вершина (точка сочленения) и мост.

Введем еще одну операцию над графом – удаление вершины.

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

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

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

Для графа 13.5 найдем все разделительные вершины и мосты:

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Студент — человек, постоянно откладывающий неизбежность. 11188 — | 7532 — или читать все.

Ссылка на основную публикацию
Скопировать контакты с андроид на компьютер
Мы уже рассказывали о том, как скопировать контакты со смартфона на смартфон. Но иногда проще перебросить контактную книгу на компьютер....
Скайп не приходят сообщения
Общение – основная цель любого мессенджера, и Скайп – не исключение. Бывает, что сообщения в Скайпе не отправляются – эта...
Скайп предыдущие версии с официального сайта
На данной странице представлены все версии Скайп для компьютера (полноценные инсталляторы скаченные с официального сайта) и телефона, выпущенные за последние...
Скопировать строку таблицы значений 1с в другую
Не претендуя на полноту описания функций и методов работы с таблицей значений 1с привожу некоторые аспекты, которые в своё время...
Adblock detector