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

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

  • автор:

Петля (граф)

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

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

См. также

Wikimedia Foundation . 2010 .

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

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

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

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

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

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

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

См. также

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

Wikimedia Foundation . 2010 .

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

Полезное

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

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

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

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

1. Определения и простейшие свойства графов

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

Графы используют в связи с развитием теории вероятности, математической логики и информационных технологий.

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

graff.jpgмультиграф.png

Мультиграф — это граф, у которого пара вершин соединены несколькими ребрами. А такие ребра, которые соединяют одну и ту же пару вершин, называют кратными . Две различные вершины графа, соединенные ребром, называются смежными .

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

Multi-pseudograph.png

Рис. 1

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

Степенью вершины называют количество ребер, выходящих из одной вершины. Для петли ребро выходит из вершины дважды. Обозначать степень вершины \(а\) будем как γ ( а ) .

На рисунке 2 изображен граф с 7 вершинами.

592px-Graph_definition_2-2.jpg

Рис. 2

Составим список степеней вершин этого графа: γ ( a ) = 1, γ ( b ) = 5, γ ( c ) = 2, γ ( d ) = 2, γ ( e ) = 3, γ ( f ) = 2, γ ( g ) = 1 .

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

Маршрут на графике — это последовательность ребер a 1 , a 2 , . a n , в которой конец одного ребра служит началом другого. Циклическим маршрут называется в том случае, если конец последнего ребра последовательности совпал с началом первого ребра.

Для графа, изображенном на рисунка 2, a 1 , a 2 , a 3 , a 7 , a 1 , a 5 — маршрут, a 6 , a 3 , a 7 — циклический маршрут, а последовательность a 7 , a 6 , a 2 , a 1 , a 4 — маршрутом не является.

592px-Graph_definition_2-2.jpg

Рис. 2

Цепь — это маршрут, в котором каждое ребро содержится не более одного раза. Цепь, являющаяся циклическим маршрутом, называется циклом .

Для графа, изображенном на рисунка 2, a 1 , a 2 , a 6 , a 7 , a 4 , a 5 , a 7 — цепь, a 2 , a 6 , a 7 , a 8 , a 4 , a 2 , a 6 — цикл.

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

Для графа, изображенном на рисунка 2, a 1 , a 2 , a 6 , a 7 , a 4 — простая цепь, a 2 , a 6 , a 7 , a 8 , a 4 — простой цикл.

Связанные верши ны — это вершины \(a\) и \(b\), для которых существует цепь, начинающаяся в \(a\) и заканчивающаяся в \(b\).

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

Один и тот же граф может быть изображен по-разному. Например, граф на рисунке 2 тот же, что и изображен на рисунке 3.

ребро, граф, вершина, дуга, петля и цикл что это такое в информатике? каждое объяснение каждого слова.

Граф — совокупность связанных между собой объектов (вершин). Вершины связываются ребрами графа. Граф бывает как направленным, так и нет. В направленном графе у ребра, соединяющего две вершины существует и направление связи от какой вершины к какой. В каждую вершину могут «входить» одно или несколько ребер и «выходить» одно или несколько.
Для не направленных графов существует просто соединение вершин.
Петля — это когда производишь переход от одной вершины к другой возможно вернуться в исходную вершину.
Цикл это когда переходя от вершины к вершине по ребрам ВСЕГДА возвращаешься в исходную вершину.

Жертва ЕГЭПрофи (658) 7 лет назад

Хорошо начали, но в конце даже я запутался.
OK, пусть ориентированные графы нас не интересуют. На простом языке:

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

По сути, петля — тоже цикл, просто очень коротенький: -)

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

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