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

Петля (граф)

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

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

См. также

Wikimedia Foundation . 2010 .

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

Петля (теория графов) — У этого термина существуют и другие значения, см. Петля. Граф, содержащий петлю при вершине 1 Петля в графе  ребро, инци­дентное одной и той же вершин … Википедия

Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф  это совокупность непустого множества вершин и множества пар… … Википедия

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

Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С … Википедия

Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) … Википедия

Длина пути в орграфе — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Дуга (теория графов) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Инцидентность — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Мультиграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Подграф — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Как найти петлю в локальной сети и как ее оперативно устранить

Сетевая петля — на самом деле , опасная штука. Очень часто ее появление связано с неправильным подсоединением линков маршрутизаторов или коммутаторов. Реже она случается из-за неверных настроек маршрутного адреса.

Как найти такую петлю, мы разберем чуть ниже. Но в целом предугадывать возникновение таких петель не получается. Ее наличие становится видимым , уже когда проявляются признаки зацикливания или когда уже полностью «ложится» вся наша сеть.

Как образуется сетевая петля

Если посмотреть на принцип «сетевой петли», то для большего понимания скажем, что это когда пакет каких-либо данных долго блуждает по одному и тому же маршрутному кругу от коммутатора к коммутатору и никак не может достичь своего конечного получателя. От этого с лучается перегрузка сети и она «ложится» , т ак как становится просто перегруженной IP-пакетами, которые не перестают множит ь ся из-за коммуникации между сетевыми устройствами. Но пакеты не покидают маршрутную сеть, а блуждают внутри сетевой петли, так и образуется сетевой шторм.

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

Как определить сетевую петлю по ее признакам

1. TTL — это временное ограничение жизни сетевого пакета;
2. IP ID — это и так понятно.

Как найти сетевую петлю в локальной сети

1. Первое , что нужно сделать , — это определить локальный участок, где происходит зацикливание. Определить н ет рудно — там возникают проблемы с И нтернетом.
2. Подберите любой сниффер и можете его запускать для определения зацикленных устройств.
3. Определите сетевые пакеты, создающие шторм , и отфильтруйте их. Найти их будет н ес ложно — их огромное количество и у многих схожий ID IP.

Мы будем очень благодарны

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

Теория Графов. Часть 2 Смежность, инцидентность, петли

Давайте рассмотрим самый обыкновенный неориентированный граф (Рисунок 1). В нем есть вершина Р и вершина К. Данные вершины являются смежными (adjacent), так как они соединены ребром РК.

Помимо этого, как мы видим, вершина К является концом ребра РК, а Р его началом, в таких случаях вершина К и Р называются инцидентными (incident) ребру РК.

Рисунок 1

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

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

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

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

В связи с тем, что выше мы рассматривали неориентированный граф, то было неважно, с какого направления определять смежность и инцидентность. Вершина Р могла быть смежна вершине К, но также мы могли сказать, что вершина К смежна вершине Р.

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

Рисунок 2

Петли

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

Петли

Заключение

В следующей статье я покажу, как с помощью матрицы задавать графы, а также покажу, что такое вес ребра.

Знакомство с графовой базой данных Neo4j

Среди жителей Кёнигсберга (нынешний Калиниград) была распространена такая загадка: как пройти по всем городским мостам через реку, не проходя ни по одному из них дважды. Многие пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

Решил задачку Леонард Эйлер, сформулировав ряд правил и доказав, что пройти по мостам, не повторяясь, невозможно.

Так и зародилась теория графов.

Что такое граф?

Граф — абстрактный математический объект, представляющий собой множество вершин (точек) и набор рёбер (линий), то есть соединений между парами вершин.

Ориентированный граф

Ориентированный граф — это граф, ребро которого имеет заданное направление между вершинами.

Петля

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

Классификация графов

Связанный граф

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

В данном примере есть путь от вершины А до вершины D, хоть он и пролегает через другие вершины.

Сильно связанный граф

Граф называется сильно связанным, если любая его вершина соединена с любой другой ребром. Если связи ориентированные — то граф называется ориентированно связанным.

Взвешенный граф

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

Мультиграф

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

Где используются графы

Графы используются в геоинформационных системах (ГИС), логистике, социальных сетях, магазинах и других сферах жизни.

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

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

Карту города тоже можно представить в виде графа.

Данный граф применим в системах навигации для поиска оптимального маршрута. Перекрестки — вершины графа, а дороги — ребра.

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

Социальный граф

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

Даже 3D-объект можно представить в виде графа:

Каждая вершина хранит координаты x, y, z.

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

Графовые базы

Первая графовая СУБД Neo4j создана в 2007 году, сейчас их уже десятки, наиболее популярные:

• ArangoDB (мультимодельная)
• HyperGraphDB (использует модель мультиграфа)
• Neo4j (использует модель ориентированного графа)
• OrientDB (позиционируется как «мультимодельная СУБД»)

Neo4j

Графовая СУБД с открытым исходным кодом, реализована на Java компанией Neo Technology.

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

Приложение может взаимодействовать с БД по одному из протоколов:

• HTTP
• HTTPS
• BOLT (Собственный протокол Neo Technology)

Продолжим знакомство с Neo4j на примере стандартной БД “Movie”

Пользователь может просматривать БД с помощью Neo4j Browser

Вершины графа в Neo4j имеют свой тип, в БД Movie у нас 2 типа вершин:
* Person (name — имя актера, born — год рождения)
* Movie (title — наименование фильма, released — год выхода)

Если проводить аналогию с реляционными базами, то Person и Movie — это таблицы.

Для работы с БД используется язык запросов Cypher.

Cypher

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

Для начала найдем актера с именем Том Хэнкс

MATCH — аналог WHERE, в круглых скобках мы описываем свойства вершины (условие поиска), а RETURN — аналог SELECT, в нем мы описываем, что вернуть.

Теперь поищем фильмы, в которых снимался Том Хэнкс.

Запрос усложнился, в MATCH мы описали вершины обоих типов, и отношение между ними (ребро) в квадратных скобках.

Теперь посмотрим, кто снимался с Томом на одной площадке, и в каком фильме:

Текст запроса приближен к текстовому отображению графа:

От вершины типа Person с именем Tom Hanks по ребру ACTED_IN находятся все вершины Movie , в которых снимался актер, от вершин типа Movie по связи ACTED_IN идет поиск всех актеров, снявшихся в каждом найденном фильме соответственно.

Где и когда использовать графовые СУБД

Графовые базы уже нашли применение в:

• Социальных сетях
• Системах рекомендаций (с этим товаром часто покупают…)
• Обработка пользовательских данных, корреляция данных из разных источников (информационный след в сети)

Если в вашем приложении планируется много сущностей и связей многие-ко-многим, то это один из признаков, что предпочтительней выбрать графовую СУБД (утверждение Martin Kleppmann’а в книге “Designing Data Intensive Applications”).

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

Выводы

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

Например, площадка medium использует Neo4j для хранения отношений между различными сущностями (Стек, который позволил Medium обеспечить чтение на 2.6 тысячелетия), а данные хранит в NoSQL БД dynamoDB.

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

• БД занимает заметно больше места на диске, по отношению к реляционным СУБД;
• На простых запросах производительность ниже, чем в реляционных базах;
• Необходимо обучать разработчиков.

Если вас заинтересовали графовые базы, то на официальном сайте Neo4j можно скачать БЕСПЛАТНО книгу с осьминогом, в ней больше информации про внутреннее устройство Neo4j и Cypher.