Что такое петля в информатике
Перейти к содержимому

Что такое петля в информатике

  • автор:

Петля (граф)

Петля́ в графе — ребро, инци­дентное одной и той же вершине.

Строго говоря, у петли нет ориентации. Однако в ориентированном графе для отличия от смешанного графа петлям придают ориентацию.

См. также

Wikimedia Foundation . 2010 .

Смотреть что такое «Петля (граф)» в других словарях:

  • Петля (теория графов) — У этого термина существуют и другие значения, см. Петля. Граф, содержащий петлю при вершине 1 Петля в графе ребро, инци­дентное одной и той же вершин … Википедия
  • Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность непустого множества вершин и множества пар… … Википедия
  • Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия
  • Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Инцидентность — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Мультиграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Подграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

1. Информационные модели на графах

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. В процессе решения задач математики заметили, что удобно изображать объекты точками, а отношения между ними — отрезками или дугами.

Основы теории графов как математической науки заложил в \(1736\) г. Леонард Эйлер , рассматривая задачу о Кёнигсбергских мостах. Сегодня эта задача стала классической.

21 28.png

Графом называется конечное множество точек, некоторые из которых соединены линиями.
Обрати внимание!
Точки называются вершинами графа, а соединяющие линии — рёбрами.

22.png

Количество рёбер, выходящих из вершины графа, называется степенью вершины .
Обрати внимание!
Вершина графа, имеющая нечётную степень, называется нечётной, а чётную степень — чётной.

23.png

Изолированная вершина — вершина, степень которой равна \(0\).
Конечная вершина графа — вершина, степень которой равна \(1\).
Направленная линия (со стрелкой) называется дугой .
Линия ненаправленная (без стрелки) называется ребром .
Линия, выходящая из некоторой вершины и входящая в неё же, называется петлёй .

24.png

Рассмотрим отношение «дети переписываются» (пишут письма друг другу). Отношение является двусторонним, поэтому вершины соединены линиями без стрелок.

25.png

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

26.png

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

Граф с двумя нечётными вершинами также можно начертить одним росчерком. Начинать движение надо с одной нечётной вершины, а заканчивать в другой.

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

В графе ребро, концы которого совпадают, то есть [math]e=(v, v)[/math] , называется петлей (англ. loop).

Два ребра, имеющие общую концевую вершину, то есть [math]e_1=(v, u_1)[/math] и [math]e_2=(v, u_2)[/math] , называются смежными (англ. adjacent).

Если имеется ребро [math] (v, u) \in E [/math] , то говорят:

  • [math] v [/math] — предок (англ. direct predecessor) [math] u [/math] .
  • [math] u [/math] и [math] v [/math] — смежные.
  • Вершина [math] u [/math] инцидентна ребру [math] (v, u) [/math] .
  • Вершина [math] v [/math] инцидентна ребру [math] (v, u) [/math] .

Инцидентность (англ. incidence) — понятие, используемое только в отношении ребра и вершины. Две вершины или два ребра не могут быть инцидентны.

Граф с [math] p [/math] вершинами и [math] q [/math] рёбрами называют [math] (p, q) [/math] -графом. [math] (1, 0) [/math] -граф называют тривиальным.

Заметим, что по определению ориентированного графа, данному выше, любые две вершины [math]u,~v[/math] нельзя соединить более чем одним ребром [math](u, v)[/math] . Поэтому часто используют другое определение.

Определение:
Ориентированным графом [math]G[/math] называется четверка [math]G = (V, E, \operatorname, \operatorname)[/math] , где [math]V[/math] и [math]E[/math] — некоторые множества, а [math]\operatorname, \operatorname : E \rightarrow V[/math] .

Данное определение разрешает соединять вершины более чем одним ребром. Такие рёбра называются кратными (иначе — параллельные, англ. multi-edge, parallel edge). Граф с кратными рёбрами принято называть мультиграфом (англ. multigraph). Если в мультиграфе присутствуют петли, то такой граф называют псевдографом (англ. pseudograph).

Петля (теория графов)

Пе́тля́ в графе — ребро, инци­дентное одной и той же вершине.

Строго говоря, у петли нет ориентации. Однако в ориентированном графе для отличия от смешанного графа петлям придают ориентацию.

См. также

  • Дополнить статью (статья слишком короткая либо содержит лишь словарное определение).
  • Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
  • Теория графов

Wikimedia Foundation . 2010 .

  • Петля (роман)
  • Петля Барнарда

Полезное

Смотреть что такое «Петля (теория графов)» в других словарях:

  • Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Цикл (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Степень вершины (теория графов) — Рис. 1. Граф, на вершинах которого отмечены степени. Степень вершины (англ. degree, также валент … Википедия
  • ГРАФОВ ТЕОРИЯ — в химии, область конечной математики, изучающая дискретные структуры, наз. графами; применяется для решения различных теоретич. и прикладных задач. Некоторые основные понятия. Граф совокупность точек (вершин) и совокупность пар этих точек (не… … Химическая энциклопедия
  • Петля (граф) — Граф, содержащий петлю при вершине 1 Петля в графе ребро, инци­дентное одной и той же вершине. Строго говоря, у петли нет ориентации. Однако в ориентированном графе для отличия от смешанного графа петлям придают ориентацию. См. также Цикл (теория … Википедия
  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия
  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия
  • Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность непустого множества вершин и множества пар… … Википедия
  • Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия
  • Обратная связь: Техподдержка, Реклама на сайте
  • �� Путешествия

Экспорт словарей на сайты, сделанные на PHP,
WordPress, MODx.

  • Пометить текст и поделитьсяИскать в этом же словареИскать синонимы
  • Искать во всех словарях
  • Искать в переводах
  • Искать в ИнтернетеИскать в этой же категории

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

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