Что такое инцидентность в графе
Основные определения теории графов
Содержание
Ориентированные графы [ править ]
| Определение: |
| Конечным графом (англ. finite graph) [math]G[/math] называется граф, в котором множества [math]V[/math] и [math]E[/math] — конечны. Следует заметить, что большинство рассматриваевых нами графов — конечны. |
| Определение: |
| Изоморфные графы (англ. isomorphic graphs) — два графа [math]A[/math] и [math]B[/math] называются изоморфными, если можно установить биекцию между их вершинами и соответствующими им рёбрами. |
Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.
Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,
Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).
Теория Графов. Часть 2 Смежность, инцидентность, петли
Ничего не сделано, если что-то осталось недоделанным. – Иоганн Гаусс
Смежность и инцидентность
Смежность и инцидентность
Давайте рассмотрим самый обыкновенный неопределённый граф (Рисунок 1). В нем есть вершина Р и вершина К. Данные вершины являются смежными (adjacent), так как они соединены ребром РК.
Помимо этого, как мы видим, вершина К является концом ребра РК, а Р его началом, в таких случаях вершина К и Р называются инцидентными (incident) ребру РК.
Рисунок 1
Смежностью вершин графа – называется отношение между двумя вершинами, в котором существует ребро их соединяющее.
Инцидентность – это когда вершина a является началом или концом ребра t. Если мы добавим еще одну вершину b, то мы скажем, что вершина a и b инцидента ребру t.
Кроме вершин, смежность присутствует и у рёбер. Рёбра просто должны иметь общую вершину. В нашем случаи мы можем сказать, что ребро ДК является смежным ребру РК, так как у них есть общая вершина К.
Смежностью рёбер графа – называется отношение между двумя рёбрами, в котором существует вершина соединяющая их.
В связи с тем, что выше мы рассматривали неопределенный граф, то было неважно, с какого направления определять смежность и инцидентность. Вершина Р могла быть смежна вершине К, но также мы могли сказать, что вершина К смежна вершине Р.
В ориентированном графе все немного по-другому (Рисунок 2), так у нас имеется направление, которое мы не в силах поменять. Если вершина 1 смежна вершине 2, то вершина 2 не может быть смежна вершине 1. То же самое касается и инцидентности. Вершины 1 и 2 инцидентны ребру 12, наоборот не работает.
Рисунок 2
Петли
Петля – это ребро инцидентное одной и той же вершине. То есть вершина которая соединена сама с собой. На рисунке ниже мы видим, как это выглядит.
Петли
Заключение
В следующей статье я покажу, как с помощью матрицы задавать графы, а также покажу, что такое вес ребра.
P.S. Если вам показалось, что эта статья была очень, очень подробной или раздутой, то сообщите об этом в комментариях, так как в своих статьях я стремлюсь к тому, чтобы люди читающие их смогли понять описываемую мною тему. Неточности и предложения о темах также пишите в комментарии.
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Инцидентность
Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице).
Ссылки
Литература
Полезное
Смотреть что такое «Инцидентность» в других словарях:
инцидентность — — [[http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23]] Тематики защита информации EN incidence … Справочник технического переводчика
ИНЦИДЕНТНОСТЬ — геометрический термин, употребляемый для обозначения отношения принадлежности (связи, соединения) между основными объектами геометрии: точками, прямыми, плоскостями. Свойства И. характеризуются так наз. аксиомами принадлежности (см., например,… … Математическая энциклопедия
инцидентность — инцид ентность, и … Русский орфографический словарь
ИНЦИДЕНТНОСТЬ — (от лат. incidens, род. падеж incidentis случающийся), число вновь выявленных (новых) случаев возникновения инфекции за определённый период на 100, 1000, 10 тыс. или 100 тыс. животных, показатель частоты заболеваний и носительства; одна из … Ветеринарный энциклопедический словарь
КОНФИГУРАЦИЯ — конечное множество точек, прямых, плоскостей, связанных между собой взаимными инцидентностями. К. могут быть как плоскими, так н пространственными. Плоская конфигурация конечная система рточек и gпрямых на плоскости, расположенных таким образом,… … Математическая энциклопедия
Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Мультиграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
Инцидентность и смежность в графах, матрицы смежности, матрицы инцидентности, списки инцидентности
Инцидентность вершин и рёбер графа, смежность вершин графа
Пример 1. Задать аналитически граф, представленный на рисунке ниже. (рис. А)
Итак, задаём граф следующими множествами:
Зададимся вопросом: можно ли поместить слона в компьютер? Ответ: можно, если слона смоделировать в виде графа, в котором вершинами являются части его тела, а рёбра соединяют те части тела, которые соединены в слоне как биологическом объекте. При этом получившийся граф должен быть представлен в памяти компьютера в понятном компьютеру виде.
В связи с широким применением графов в программировании и информационных технологиях вообще возникает вопрос о представлении графа в виде структуры данных. Различные способы представления графов в памяти компьютера отличаются объёмом занимаемой памяти и скоростью выполнения операций над графами.
Матрицы смежности
Матрица смежности для неориентированного графа
Элемент матрицы смежности s ij неориентированного графа определяется следующим образом:
— равен единице, если вершины v i и v j смежны;
— равен нулю, если вершины v i и v j не смежны.
Пример 2. Составить матрицу смежности для графа, представленного на рисунке ниже.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 1 |
| 3 | 1 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 |
Таким образом, матрица смежности неориентированного графа симметрична относительно главной диагонали.
Матрица смежности для ориентированного графа
Элемент матрицы смежности s ij ориентированного графа определяется следующим образом:
— равен единице, если из вершины v i в вершину v j входит дуга;
— равен нулю, если из вершины v i в вершину v j дуга не входит.
Пример 3. Составить матрицу смежности для графа, представленного на рисунке ниже.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 | 0 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 |
Таким образом, матрица смежности ориентированного графа не симметрична.
Матрица смежности для графа с кратными рёбрами
Пример 4. Составить матрицу смежности для графа, представленного на рисунке ниже.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 3 | 2 | 0 | 0 |
| 2 | 3 | 0 | 0 | 1 | 1 |
| 3 | 2 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 |
Матрица смежности для взвешенного графа
В случае взвешенного графа элемент матрицы смежности s ij равен числу w, если существует ребро между вершинами v i и v j с весом w. Элемент s ij равен нулю, если рёбер между вершинами v i и v j не существует.
Пример 5. Составить матрицу смежности для графа, представленного на рисунке ниже.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 11 | 9 | 0 | 0 |
| 2 | 11 | 0 | 0 | 5 | 8 |
| 3 | 9 | 0 | 0 | 0 | 2 |
| 4 | 0 | 5 | 0 | 0 | 0 |
| 5 | 0 | 8 | 2 | 0 | 0 |
Матрицы инцидентности
Матрица инцидентности для неориентированного графа
Элемент матрицы инцидентности для неориентированного графа h ij определяется следующим образом:
— равен единице, если вершина v i инцидентна ребру e j ;
Пример 6. Составить матрицу инцидентности для графа, представленного на рисунке ниже.
| V | 1-2 | 1-3 | 2-4 | 2-5 | 3-5 |
| 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 1 | 1 |
Матрица инцидентности для ориентированного графа
Элемент матрицы инцидентности для ориентированного графа h ij определяется следующим образом:
— равен минус единице, если вершина v i является началом ребра e j ;
— равен единице, если вершина v i является концом ребра e j ;
Пример 7. Составить матрицу инцидентности для графа, представленного на рисунке ниже.
| V | 1-2 | 1-3 | 2-4 | 2-5 | 3-5 |
| 1 | 1 | -1 | 0 | 0 | 0 |
| 2 | -1 | 0 | -1 | -1 | 0 |
| 3 | 0 | 1 | 0 | 0 | -1 |
| 4 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 1 | 1 |
Списки инцидентности
Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности.
Список инцидентности одной вершины графа включает номера вершин, смежных с ней.
Ссылки на начало этих списков образуют одномерный массив, индексами которого служат номера вершин графа.
Пример 8. Составить списки инцидентности для графа, представленного на рисунке ниже.
Преимущества и недостатки каждого способа
Матрицы смежности и инцидентности целесообразнее использовать когда:
Из-за последнего обстоятельства матрицы чаще используются в теоретических исследованиях графов.
Списки инцидентности целесообразнее использовать когда:
На практике списки чаще используются в прикладных целях.
Теория Графов. Часть 2 Смежность, инцидентность, петли
Ничего не сделано, если что-то осталось недоделанным. – Иоганн Гаусс
Смежность и инцидентность
Смежность и инцидентность
Давайте рассмотрим самый обыкновенный неориентированный граф (Рисунок 1). В нем есть вершина Р и вершина К. Данные вершины являются смежными (adjacent), так как они соединены ребром РК.
Помимо этого, как мы видим, вершина К является концом ребра РК, а Р его началом, в таких случаях вершина К и Р называются инцидентными (incident) ребру РК.
Рисунок 1
Смежностью вершин графа – называется отношение между двумя вершинами, в котором существует ребро их соединяющее.
Инцидентность – это когда вершина a является началом или концом ребра t. Если мы добавим еще одну вершину b, то мы скажем, что вершина a и b инцидента ребру t.
Кроме вершин, смежность присутствует и у рёбер. Рёбра просто должны иметь общую вершину. В нашем случаи мы можем сказать, что ребро ДК является смежным ребру РК, так как у них есть общая вершина К.
Смежностью рёбер графа – называется отношение между двумя рёбрами, в котором существует вершина соединяющая их.
В связи с тем, что выше мы рассматривали неориентированный граф, то было неважно, с какого направления определять смежность и инцидентность. Вершина Р могла быть смежна вершине К, но также мы могли сказать, что вершина К смежна вершине Р.
В ориентированном графе все немного по-другому (Рисунок 2), так у нас имеется направление, которое мы не в силах поменять. Если вершина 1 смежна вершине 2, то вершина 2 не может быть смежна вершине 1. То же самое касается и инцидентности. Вершины 1 и 2 инцидентны ребру 12, наоборот не работает.
Рисунок 2
Петли
Петля – это ребро инцидентное одной и той же вершине. То есть вершина которая соединена сама с собой. На рисунке ниже мы видим, как это выглядит.
Петли
Заключение
В следующей статье я покажу, как с помощью матрицы задавать графы, а также покажу, что такое вес ребра.