Что такое герцог в информатике
Граф (теория графов)
В математической теории графов и информатике граф — это совокупность объектов со связями между ними.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами. Например, строение Википедии можно смоделировать при помощи ориентированного графа (орграф), в котором вершины — это статьи, а дуги (ориентированные рёбра) — это связи, созданные гиперссылками (см. Тематическая карта).
Содержание
Определения
Теория графов не обладает устоявшейся терминологией. В различных статьях под одними и теми же терминами понимаются разные вещи. Приводимые ниже определения — наиболее часто встречаемые.
V (а значит и E ) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.
Два ребра называются смежными, если они имеют общую концевую вершину.
Два ребра называются кратными, если множества их концевых вершин совпадают.
Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).
Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.
Ориентированный граф
Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v 
w ведёт от вершины v к вершине w.
Смешанный граф
Понятно, что ориентированный и неориентированный графы являются частными случаями смешанного.
Прочие связанные определения
Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Ориентированным путём в орграфе называют конечную последовательность вершин vi 
, для которой все пары (vi,vi + 1) 
являются (ориентированными) рёбрами.
Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.
Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:
Бинарное отношение на множестве вершин графа, заданное как «существует путь из u в v », является отношением эквивалентности, и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояния между вершинами как минимальную длину пути, соединяющего эти вершины.
Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа G. Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов
Ребро графа называется мостом, если его удаление увеличивает число компонент.
Дополнительные характеристики графов
Способы представления графа в информатике
Матрица смежности
Матрица смежности — таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).
Недостатком являются требования к памяти — очевидно, квадрат количества вершин.
Матрица инцидентности
Данный способ является самым ёмким (размер пропорционален | E | | V | ) и неудобным для хранения, но облегчает нахождение циклов в графе.
Список рёбер
Список рёбер — это тип представления графа в памяти, подразумевающий, что каждое ребро представляется двумя числами — номерами вершин этого ребра. Список рёбер более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности.
Обобщение понятия графа
Простой граф является одномерным симплициальным комплексом.
Более абстрактно, граф можно задать как тройку 
, где V и E — некоторые множества (вершин и рёбер, соотв.), а 
— функция инцидентности (или инцидентор), сопоставляющая каждому ребру 
(упорядоченную или неупорядоченную) пару вершин u и v из V (его концов). Частными случаями этого понятия являются:
Под данное выше определение не подходят некоторые другие обобщения:
Литература
См. также
Ссылки
Популярные программы для визуализации графов
Алгоритмы на графах — Часть 0: Базовые понятия
Как оказалось тема алгоритмов интересна Хабра-сообществу. Поэтому я как и обещал, начну серию обзоров «классических» алгоритмов на графах.
Так как публика на Хабре разная, а тема интересна многим, я должен начать с нулевой части. В этой части я расскажу что такое граф, как он представлен в компьютере и зачем он используется. Заранее прошу прощения у тех кто это все уже прекрасно знает, но для того чтобы объяснять алгоритмы на графах, нужно сначала объяснить что такое граф. Без этого никак.
В математике, Граф — это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин, а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами).
Граф может быть ориентированным или неориентированным. В ориентированном графе, связи являются направленными (то есть пары в E являются упорядоченными, например пары (a, b) и (b, a) это две разные связи). В свою очередь в неориентированном графе, связи ненаправленные, и поэтому если существует связь (a, b) то значит что существует связь (b, a).
Неориентированный граф: Соседство (в жизни). Если (1) сосед (3), то (3) сосед (1). См рис. 1.а
Ориентированный граф: Ссылки. Сайт (1) может ссылаться на сайт (3), но совсем не обязательно (хотя возможно) что сайт (3) ссылается сайт (1). См рис. 1.б
Путь в графе это конечная последовательность вершин, в которой каждые две вершины идущие подряд соединены ребром. Путь может быть ориентированным или неориентированным в зависимости от графа. На рис 1.а, путем является например последовательность [(1), (4), (5)] на рис 1.б, [(1), (3), (4), (5)].
У графов есть ещё много разных свойств (например они могут быть связными, двудольными, полными), но я не буду описывать все эти свойства сейчас, а в следующих частях когда эти понятия понадобятся нам.
Представление графов
Существует два способа представления графа, в виде списков смежности и в виде матрицы смежности. Оба способа подходят для представления ориентированных и неориентированных графов.
Матрица смежности
Этот способ является удобным для представления плотных графов, в которых количество рёбер (|E|) примерно равно количеству вершин в квадрате (|V| 2 ).
В данном представлении мы заполняем матрицу размером |V| x |V| следущим образом:
A[i][j] = 1 (Если существует ребро из i в j)
A[i][j] = 0 (Иначе)
Данный способ подходит для ориентированных и неориентированных графов. Для неориентированных графов матрица A является симметричной (то есть A[i][j] == A[j][i], т.к. если существует ребро между i и j, то оно является и ребром из i в j, и ребром из j в i). Благодаря этому свойству можно сократить почти в два раза использование памяти, храня элементы только в верхней части матрицы, над главной диагональю)
Понятно что с помощью данного способа представления, можно быстро проверить есть ли ребро между вершинами v и u, просто посмотрев в ячейку A[v][u].
С другой стороны этот способ очень громоздкий, так как требует O (|V| 2 ) памяти для хранения матрицы.
На рис. 2 приведены представления графов из рис. 1 с помощью матриц смежности.
Списки смежности
Данный способ представления больше подходит для разреженных графов, то есть графов у которых количество рёбер гораздо меньше чем количество вершин в квадрате (|E| 2 ).
В данном представлении используется массив Adj содержащий |V| списков. В каждом списке Adj[v] содержатся все вершины u, так что между v и u есть ребро. Память требуемая для представления равна O (|E| + |V|) что является лучшим показателем чем матрица смежности для разреженных графов.
Главный недостаток этого способа представления в том, что нет быстрого способа проверить существует ли ребро (u, v).
На рис. 3 приведены представления графов из рис. 1 с помощью списков смежности.
Применение
Те кто дочитал до этого места, наверное задали себе вопрос, а где же собственно я смогу применить графы. Как я и обещал я буду стараться приводить примеры. Самый первый пример который приходит в голову это социальная сеть. Вершинами графа являются люди, а ребрами отношения (дружба). Граф может быть неориентированным, то есть я могу дружить только с теми кто дружит со мной. Либо ориентированным (как например в ЖЖ), где можно добавить человека в друзья, без того чтобы он добавлял вас. Если же он да добавит вас вы будете «взаимными друзьями». То есть будет существовать два ребра: (Он, Вы) и (Вы, Он)
Ещё одно из применений графа, которое я уже упоминал это ссылки с сайта на сайт. Представим Вы хотите сделать поисковую систему и хотите учесть на какие сайты есть больше ссылок (например сайт A), при этом учитывать сколько сайтов ссылается на сайт B, который ссылается на сайт A. У вас будет матрица смежности этих ссылок. Вы захотите ввести какую то систему подсчёта рейтинга, которая делает какие то подсчёты на этой матрице, ну, а дальше… это Google (точнее PageRank) =)
Заключение
Это небольшая часть теории которая понадобится нам чтобы для следующих частей. Надеюсь вам было понятно, а главное понравилось и заинтересовало читать дальнейшие части! Оставляйте свои отзывы и пожелания в комментариях.
В следующей части
BFS — Алгоритм поиска в ширину
Библиография
Кормен, Лайзерсон, Риверст, Штайн — Алгоритмы. Построение и анализ. Издательство Вильямс, 2007.
Словарь терминов теории графов
Граф — статья в английской Википедии
Статья это кросс-пост из моего блога — «Programing as is — записки программиста»
Графы: основы теории, алгоритмы поиска
Aug 22, 2020 · 6 min read
Возможно, вы уже знакомы с понятием спортивного программирования и знаете, что оно помогает развить навыки решения проблем и прокачать технические знания о структурах данных и алгоритмах.
Одной из важнейших составляющих спортивного программирования является изучение алгоритмов. В этой статье мы охватим большое количество алгоритмов, в том числе все алгоритмы на графах, знание которых понадобится вам для успешного решения задач из теории графов на соревнованиях по программированию. Конечно, одних теоретических знаний алгоритмов недостаточно, и вам придётся набить руку в решении практических задач на таких сайтах, как Codeforces. Настоящая же статья представит вам инструменты, необходимые для освоения важных графовых алгоритмов. Итак, приступим.
Что такое граф?
Г р афы, в понимании программистов, — это не те графики, которые мы изучали в школе. Это не столбиковые диаграммы или гистограммы.
С точки зрения компьютерных наук и дискретной математики, графы — это абстрактный способ представления типов отношений, например дорог, соединяющих города, и других видов сетей. Графы состоят из рёбер и вершин. Вершина — это точка на графе, а ребро — это то, что соединяет две точки на графе.
В условиях задач из теории графов на соревнованиях по программированию обычно говорится о таких вещах, как сети и решётки.
Вот список всех терминов, относящихся к теории графов, которые вам нужно знать:
Представление графов в коде
Для того, чтобы использовать алгоритмы на графах в коде, сначала нам нужно разобраться, как осуществляется представление графов в коде. Весь следующий код будет на C++, так как для спортивного программирования я предпочитаю именно этот язык за его скорость и встроенные функции, позволяющие упростить написание решений задач.
Будут показаны два способа представления графов: матрицы смежности и списки смежности. Больше вам пригодится представление графов в виде списка смежности.
Матрицы смежности
Матрица смежности представляет собой граф в виде двумерной матрицы с размерами V x V, где V — количество вершин графа. Матрицы смежности лучше всего применять, когда V² примерно равно E (числу рёбер), то есть когда граф плотный. Запись a_ij обозначает, сколько рёбер соединяют вершину i и вершину j.
Списки смежности
Другой распространенный способ представления графов в коде — списки смежности. Суть в том, что вы создаёте списки соседей для каждой вершины, а затем помещаете все эти списки в другой список. Их лучше всего применять, когда в графе небольшое количество рёбер, то есть когда граф разрежённый. Если у вас взвешенный граф, т.е. каждое ребро графа имеет какой-то вес, то в списке будут содержаться пары для рёбер (сосед, вес).
Поиск в глубину
Теперь, когда мы научились представлять графы в коде, можем приступить к изучению некоторых алгоритмов на графах! Начнём с поиска в глубину (DFS) и завершим поиском в ширину (BFS). Чтобы не загромождать статью, алгоритмы поиска пути не будут здесь рассматриваться (интересующиеся могут ознакомиться с алгоритмом поиска кратчайшего пути Беллмана-Форда).
Поиск в глубину — это один из базовых алгоритмов на графах. Он применяется для поиска расстояния от одной вершины до других вершин в графе. Это алгоритм обхода.
Поиск в глубину помечает каждую вершину в графе одной из двух меток: посещённая или не посещённая. Алгоритм помечает каждую вершину как посещённую, если удаётся избежать циклов. Он работает следующим образом:
Поиск в ширину
Поиск в ширину — ещё один алгоритм обхода графов. Вместе с алгоритмом поиска вглубь он составит большую часть увлекательных соревнований по программированию, по крайней мере, тех из них, что относятся к графам.
Поиск в ширину тоже помещает каждую вершину в графе в одну из двух категорий: посещённых или непосещённых. И цель у обоих алгоритмов одна и та же: помечать каждую вершину в графе как посещённую, если удаётся избежать циклов. Вот как работает алгоритм поиска в ширину:
Как видите, алгоритм поиска в ширину очень похож на алгоритм поиска в глубину. Однако вместо того, чтобы спускаться вниз по ветви графа или дерева, как это делает алгоритм поиска в глубину, алгоритм поиска в ширину проходит каждый уровень.
Заключение
Освоив теоретическую часть, касающуюся двух самых важных алгоритмов обхода на графах, вам остаётся только практиковаться, чтобы использовать эти алгоритмы в соревнованиях по программированию. Я бы порекомендовал для начала Codeforces: решайте задачи, помеченные тегами bfs и dfs с рейтингом до 1400. Когда почувствуете, что справляетесь с ними, увеличьте сложность.
Отработка навыков решения алгоритмических задач, особенно алгоритмов на графах, поможет вам побеждать на соревнованиях по программированию и успешно проходить технические собеседования. Вперёд — к успехам!
Графические информационные модели. Графы
Урок 6. Информатика 9 класс ФГОС
В данный момент вы не можете посмотреть или раздать видеоурок ученикам
Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобрев в каталоге.
Получите невероятные возможности
Конспект урока «Графические информационные модели. Графы»
Граф – это совокупность объектов со связями между ними. Графически это будет выглядеть следующим образом:
Вершины (точки) – это объекты, а ребра (линии между ними) – это связи. Помимо точек вершины графа могут изображаться овалами, кругами, прямоугольниками и так далее. Связи между вершинами могут быть различными: дуги, рёбра, петли.
На данном уроке мы с вами познакомимся с ориентированными и неориентированными графами. В ориентированном графе связями между вершинами будут дуги, а в неориентированном – рёбра.
Решим задачу: В соревнованиях по шахматам участвовало 6 учащихся с 9 по 11 класс. При встрече они все обменялись рукопожатиями. Вопрос: сколько всего было сделано рукопожатий?
Для решения данной задачи будем использовать граф. Вершинами графов будут являться шесть учащихся, которые участвовали в турнире. Пронумеруем их от одного до шести. Проведем от каждой вершины линии (ребра) к оставшимся пяти вершинам.
Для ответа на вопрос остается сосчитать, сколько линий изображено на графе. Ответ: на турнире было сделано 15 рукопожатий.
Взвешенный граф – это граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией – весами вершин или рёбер.
Давайте сами нарисуем взвешенный граф на основе задачи со следующим условием: Между городами A, B, C, D, Е построены дороги. Необходимо найти кратчайший путь из города А в город Е, если известно, что из города А в город В расстояние 100 километров, из А в С – 260 километров, из В в С – 140 километров, из В в Е – 400 километров, из С в D – 50 километров, из С в Е – 100 километров и из D в Е – 40 километров.
Итак, для решения данной задачи необходимо нарисовать взвешенный граф, так как нам дано расстояние, то есть вес рёбер. Для начала нарисуем вершину А. Из неё будут выходить два ребра в вершины В и С. Ребро из А в В будет короче, чем из А в С, так как расстояние из пункта А в пункт В 100 километров, а из пункта А в пункт С – 260 километров.
Далее нарисуем ребро из В в С и его вес будет равен 140.
Теперь нарисуем ребро из вершины С в вершину D и укажем вес 50
У нас получился взвешенный граф.
Нам осталось найти кратчайший путь. Для этого из вершины А будем идти в вершину В – это 100 километров, затем сразу в вершину Е. Слаживаем 100 и 400, получим 500 километров.
В свою очередь, цикл – это цепь, в которой начальная и конечная вершины совпадают. В детстве, наверное, каждый из вас рисовал звезду, не отрывая ручки от бумаги и не проходя дважды по одной и той же линии или ребру. При изображении такой звезды начальная и конечная вершины совпадают. Сеть – это граф с циклом.
Разберём ещё один пример. У Антона в семье есть мама Татьяна, папа Юрий и сестра Маша. Изобразим каждого члена семьи как вершину нашего графа и обозначим первыми буквами имён. От каждого из них проведём рёбра к оставшимся троим. Над каждым из рёбер укажем, кто кем и кому приходится. Например, если идти от вершины Антона к Юрию, то Антон является сыном. А если идти наоборот, от Юрия к Антону, то Юрий является отцом. Аналогичным образом можно провести отношения между всеми членами семьи. Данный граф является примером семантической, или же смысловой сети.
Таким образом, Семантическая сеть – это информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними. Все связи данного графа различны, поэтому их необходимо подписывать.
Графы широко распространены как информационные модели. Их можно применять, например, при планировании жилого района, где вершинами будут являться дома, а рёбрами – дороги или дорожки, которые их связывают. Ещё одним примером будет являться карта проезда по городу на любом из видов транспорта, где остановки – это вершины, а путь движения транспорта – это рёбра и так далее.
Следующее определение в данной теме: дерево. Дерево – это граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину. Отличительная особенность дерева: между любыми двумя его вершинами существует единственный путь. Корень дерева – это одна и единственная главная его вершина.
Каждая вершина дерева (кроме корня) имеет только одного предка. Обозначенный предком объект входит в один класс высшего уровня. Любая вершина дерева может порождать несколько потомков. Потомки – это вершины, которые соответствуют классам нижнего уровня. Такой принцип связи называется «один-ко-многим». Листья – это вершины, которые не имеют потомков.
Разберёмся более подробно на примере:
Ученик Антон решил составить генеалогическое дерево своей семьи. Для этого ему необходимо было узнать, кто в каких отношениях находится. То есть он является сыном своего отца Юрия и мамы Татьяны. В свою очередь Татьяна является дочерью Леонида (дедушки Антона) и Елены (бабушки Антона). Юрий является сыном Григория (дедушки Антона) и Марии (бабушки Антона). У Антона есть сестра Маша. Так как словесное описание трудно для восприятия, давайте поможем Антону представить это все в виде дерева и построим генеалогическое дерево.
Видим, что самыми старшими являются дедушки и бабушки Антона, поэтому расположим их в самом верху. У Леонида и Елены есть дочь Татьяна, а у Григория и Марии сын Юрий. Значит, разместим их на втором уровне (если считать сверху) и укажем их отношения с родителями в виде стрелок. У Татьяны и Юрия есть сын Антон и дочь Маша. Разместим их аналогичным образом на нашей схеме.
Таким образом, мы построили родословное дерево.
· Граф – это совокупность объектов со связями между ними.
· Вершины – это объекты, а ребра – это связи.
· Взвешенный граф – это граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией – весами вершин или рёбер.
· Цепь – это путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
· Цикл – это цепь, в которой начальная и конечная вершины совпадают.
· Сеть – это граф с циклом.
· Семантическая сеть – это информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.
· Дерево – это граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину.