[Сетевые технологии, Математика, Машинное обучение, Искусственный интеллект, Химия] Теория Графов. Часть 2 Смежность, инцидентность, петли

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
04-Июл-2021 01:31

Цитировать

Ничего не сделано, если что-то осталось недоделанным. – Иоганн ГауссВ этой статье:

Смежность и инцидентность
Петли

Смежность и инцидентностьДавайте рассмотрим самый обыкновенный неопределённый граф (Рисунок 1). В нем есть вершина Р и вершина К. Данные вершины являются смежными (adjacent), так как они соединены ребром РК. Помимо этого, как мы видим, вершина К является концом ребра РК, а Р его началом, в таких случаях вершина К и Р называются инцидентными (incident) ребру РК.

Рисунок 1

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

Инцидентность – это когда вершина a является началом или концом ребра t. Если мы добавим еще одну вершину b, то мы скажем, что вершина a и b инцидента ребру t.

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

Смежностью рёбер графа – называется отношение между двумя рёбрами, в котором существует вершина соединяющая их.

В связи с тем, что выше мы рассматривали неопределенный граф, то было неважно, с какого направления определять смежность и инцидентность. Вершина Р могла быть смежна вершине К, но также мы могли сказать, что вершина К смежна вершине Р. В ориентированном графе все немного по-другому (Рисунок 2), так у нас имеется направление, которое мы не в силах поменять. Если вершина 1 смежна вершине 2, то вершина 2 не может быть смежна вершине 1. То же самое касается и инцидентности. Вершины 1 и 2 инцидентны ребру 12, наоборот не работает.

Рисунок 2ПетлиПетля – это ребро инцидентное одной и той же вершине. То есть вершина которая соединена сама с собой. На рисунке ниже мы видим, как это выглядит.

ПетлиЗаключениеВ следующей статье я покажу, как с помощью матрицы задавать графы, а также покажу, что такое вес ребра. P.S. Если вам показалось, что эта статья была очень, очень подробной или раздутой, то сообщите об этом в комментариях, так как в своих статьях я стремлюсь к тому, чтобы люди читающие их смогли понять описываемую мною тему. Неточности и предложения о темах также пишите в комментарии.
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_setevye_tehnologii (Сетевые технологии), #_matematika (Математика), #_mashinnoe_obuchenie (Машинное обучение), #_iskusstvennyj_intellekt (Искусственный интеллект), #_himija (Химия), #_grafy (графы), #_petli (петли), #_algoritmy (алгоритмы), #_kompjuternye_seti (компьютерные сети), #_matematika (математика), #_fizika (физика), #_vershina (вершина), #_rebro (ребро), #_setevye_tehnologii (сетевые технологии), #_rebra_grafa (ребра графа), #_setevye_tehnologii (
Сетевые технологии
), #_matematika (
Математика
), #_mashinnoe_obuchenie (
Машинное обучение
), #_iskusstvennyj_intellekt (
Искусственный интеллект
), #_himija (
Химия
)

Профиль ЛС

Ответить на тему

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

Текущее время: 22-Ноя 06:05
Часовой пояс: UTC + 5