Как называется набор вершин соединенных ребрами

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

Графом $G$ называется пара множеств $G = (V, E$, где $V(G)$ — непустое конечное множество элементов, называемых вершинами графа, а $E$ — множество пар элементов из $V$ (необязательно различных), называемых ребрами графа. $E = \<(u , v)\ | u, v \in V\>$ — множество ребер графа $G$, состоящее из пар вершин $(u, v)$. Ребро $(u, v)$ соединяет вершины $u$ и $v$.

Граф — это набор вершин (точек) и соединяющих их отрезков (рёбер).

Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах $N$ — количество вершин, а $M$ — ребер. Количество ребер, исходящее из вершины называют степенью вершины $d(v)$. Для вершины $a$ ребро $(a, b)$ называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).

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

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

Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.

Дерево — это связный неориентированный граф без циклов.

1) У дерева с хотя бы 2 вершинами всегда есть висячая вершина — вершина степени 1.

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

2) У дерева с хотя бы 2 вершинами всегда есть две висячие вершины.

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

3) У дерева с $N$ вершинами всегда ровно $N-1$ ребро.

Давайте отрезать от дерева его висячие вершины — при этом число вершин уменьшится на один, число ребер тоже уменьшится на один, а граф останется деревом. Раз граф остается деревом, у него все время будет висячая вершина, пока $N > 1$. В какой-то момент останется только одна вершина и ноль ребер. Раз мы отрезали столько же вершин, сколько ребер, и получили 1 вершину и 0 ребер, значит изначально вершин было ровно на одну больше.

4) Между любыми двумя вершинами в дереве есть ровно один простой путь.

Действительно, если их два, то в графе есть цикл. Быть ноль их не может — ведь граф связный.

5) Дерево — это минимальный по числу рёбер связный граф на $N$ вершинах.

Действительно, если есть связный граф, в котором меньше, чем $N-1$ ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве $N-1$ ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то.

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin

Лекция «Сети и теория графов»

Учебные цели: формирование представления о графе и его основных характеристиках.

Тип: Лекция
Автор: Екатерина Калинина
Трудомкость: 2 ч.
Тема: Основы сетевого анализа

Основу теории графов заложила так называемая «Задача о кёнигсбергских мостах», на сегодняшний день ставшая классической. Суть задачи состоит в следующем:

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

Издавна гостей Кёнигсберга интересовал вопрос: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался этой задачей, после чего привел строгое доказательство того, что сделать это невозможно. Результаты исследования Эйлера заложили основу теории графов и отлично иллюстрируют направление её развития в настоящее время.

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

Вершины, в зависимости от контекста задачи, могут изображать точки назначения (города, острова, местоположения людей и т.п.), узлы связи (в компьютерных сетях), конкретных людей или адресатов и т.д. Значения рёбер также зависит от условий задачи – они могут обозначать как пути между вершинами, так и связи разного рода (социальные, экономические, физические и т.п.). Поэтому сейчас все чаще выделяют особые виды графов в рамках конкретных областей применения: социальные, молекулярные, веб‑графы и др.

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

Говорят, что ребро инцидентно вершине, если эта вершина является концом данного ребра.
Два ребра называются смежными, если они имеют общую концевую вершину. Две вершины, инцидентные одному ребру, также называют смежными.
Два ребра называются кратными, если множества их концевых вершин совпадают.
Ребро называется петлёй, если его концы совпадают.
Степень вершины – это количество рёбер, концом которых она является. Если вершине не инцидентно ни одно ребро, такую вершину называют изолированной.
Путь в графе – это любая последовательность вершин, в которой каждые две соседние вершины соединены ребром.
Цикл в графе – это путь, у которого начальная и конечная вершина совпадают.

Основные виды графов:

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

Синонимичным к понятию «граф» является понятие «сеть». Однако сетями чаще всего называют такие графы, вершины которых определенным образом помечены, т.е. несут смысловую нагрузку. Таким образом, графом чаще называют строгий математический объект, к которому применимы все законы теории графов, о сетях чаще говорят в контексте прикладных (социологических, биологических, химических и т.д.) исследований.

Базовые понятия сетей:

узлы (в графах: вершины);
связи (в графах: рёбра).

Теория сетей и сетевой анализ находят свое применение в различных областях науки, техники, а также повседневной деятельности людей:

транспортные системы и сети перевозок;
инженерные сети;
биологические сети;
нейросети (и искусственный интеллект);
социальные сети;
нарративные (повествовательные) сети;
компьютерные сети и др.

Литература

Тематические проекты, онлайн-курсы и программное обеспечение

Библиографическая ссылка: Калинина Е. Сети и теория графов // Изучаем Digital Humanities [Электронный ресурс]. 2018. URL: https://dhumanities.ru/?p=1850

контакты

Динара Амировна Гагарина, сооснователь DH CLOUD Community

Понятие и представление графа: матрица смежности, список смежности

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

Ну а более формально, граф — комбинация набора вершин и набора рёбер. Вершины — это города, а рёбра — дороги. Визуально граф можно представить так:

Граф из шести вершин

Этот граф состоит из 6 вершин, пронумерованных начиная с единицы, и 7 двухсторонних рёбер. Рёбра обычно записывают в виде пар вершин, которые они соединяют: $1$-$2$, $1$-$5$, $2$-$3$, $2$-$5$, $3$-$4$, $4$-$5$, $4$-$6$.

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

Мы уже упоминали, что “дороги” в графе могут быть как односторонними, так и двухсторонними. Для этого свойства существует отдельный термин: односторонние “дороги” называются ориентированными рёбрами (или дугами), а двухсторонние — неориентированными.

Граф, в котором все рёбра неориентированные, также называют неориентированным, а граф с ориентированными рёбрами, соответственно, ориентированным.

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

Пути и циклы

Путём в графе называется последовательность вершин, каждая из которых соединена со следующей ребром. Чаще всего под “путём” подразумевают простой путь, все вершины которого различны. Путь, который проходит через какую-либо вершину более одного раза называют сложным путём.

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

Приведём примеры на этом графе:

Циклический граф

Из множества возможных простых путей самый длинный: $a — f — c — d — e — b — h$ (существуют и другие пути с такой же длиной).

Циклом является путь $b — c — d — e — b$ (выделен цветом). Можно начать и с любой другой вершины, например, $c — d — e — b — c$.

Кратные рёбра и петли

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

Мультиграф

Красным выделены кратные рёбра, а синим — петли.

Мультиграфы встречаются в задачах реже чем обычные графы (называемые простыми), но всё же встречаются, поэтому стоит иметь о них элементарное представление.

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

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

Граф с одним штрихованным ребром

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

Определение дерева

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

Дерево — это связный граф без циклов, петель и кратных рёбер.

Все изображённые графы являются деревьями:

Среди множества свойств деревьев можно выделить два самых известных:

Количество рёбер связано с количеством вершин формулой $E = V — 1$.
Между любой парой вершин существует ровно один путь.

Матрица смежности

Существует два основных способа представления графов в программировании. Один из них, матрица смежности, используется гораздо реже, но очень просто реализуется. Граф из $N$ вершин задаётся матрицей (двумерным массивом) $N * N$, в которой $g[i][j]$ — логическое значение, true или false , обозначающее, существует ли ребро из вершины $i$ в вершину $j$.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

using namespace std; bool graph[1000][1000]; int main()  int n, m; //количество вершин и рёбер соответственно cin >> n >> m; for (int i = 0; i  m; i++)  int u, v; //номера вершин, соединённых очередным ребром cin >> u >> v; u--, v--; //Здесь стоит остановиться и вдуматься. //Чаще всего в задачах вершины будут нумероваться с 1 до N, //в отличие от индексации массивов в C++. //У этой проблемы есть два решения. //Первое: работать с номерами "как есть": создавать массивы размером N + 1, //использовать циклы от 1 до N, и т.д. //Второе: уменьшать номера вершин на единицу при вводе, и увеличивать обратно при выводе //Какое из них использовать - ваш личный выбор. //Для меня 1-индексация в С++ выглядит очень чужеродно, поэтому я использую второе решение. graph[u][v] = graph[v][u] = true; //Если бы граф был ориентированным, то обратное ребро мы бы не создавали. > for (int i = 0; i  n; i++)  int c = 0; for (int j = 0; j  n; j++)  if (graph[i][j])  c++; > > cout  <c  <" edges adjacent to vertex "  <i + 1  <endl; > >

Преимущества матрицы смежности:

Сложность проверки наличия ребра между двумя вершинами: $O(1)$

Недостатки матрицы смежности:

Занимает $N^2$ памяти, что неприемлемо для достаточно больших графов.
Сложность перебора всех вершин, смежных с данной: $O(N)$

Список смежности

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

Решим ту же задачу с использованием списка смежности (и С++11 для for-each):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

using namespace std; vectorint> graph[100000]; //массив из 100000 векторов. int main()  int n, m; cin >> n >> m; for (int i = 0; i  m; i++)  int u, v; cin >> u >> v; u--, v--; graph[u].push_back(v); graph[v].push_back(u); > for (int i = 0; i  n; i++)  int c = 0; for (int v: graph[i])  //можно было бы просто записать "int c = graph[i].size();", c++; //но такая реализация показывает, как можно перебирать > //соседние вершины. cout  <c  <" edges adjacent to vertex "  <i + 1  <endl; > >

Если требуется также удалять рёбра, то вместо вектора нужно использовать std::set .

Преимущества списка смежности:

Использует $O(M)$ памяти, что оптимально.
Позволяет быстро перебирать соседей вершины.
Позволяет за $O(\log N)$ проверять наличие ребра и удалять его (при использовании std::set ).

Недостатки списка смежности:

При работе с насыщенными графами (количество рёбер близко к $N^2$) скорости $O(\log N)$ может не хватать (единственный повод использовать матрицу смежности).
Для взвешенных графов приходится хранить vector> , что усложняет код.

brestprog

Олимпиадное программирование в Бресте и Беларуси

Особенности решения задачи единого государственного экзамена на нахождение путей в графе

Сафонова Людмила Анатольевна

Мордовский государственный педагогический университет имени М.Е. Евсевьева

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

В едином государственном экзамене по информатике на решение с помощью графа отводиться две задачи (№ 1, 13). Разберём задачу №13 из ДЕМО версии ЕГЭ по информатике 2021 на нахождение путей в графе. Но для начала вспомним, что такое графы и для чего они нужны.

Итак, граф – это не королевское должностное лицо, а абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединение между парами вершин [1] (рисунок 1 «Граф», рисунок 2 «Граф – математический объект»).

Рисунок 2 «Граф – математический объект»

Многие объекты в нашей жизни могут быть смоделированы при помощи графа. Так например, транспортная схема метрополитена, изображенная в виде станций, соединенных линиями. В терминах графа станции называются вершинами графа, а линии ребра (рисунок 3 «Схема метрополитена»).

Рисунок 3 «Схема метрополитена»

Существуют графы: ориентированные и неориентированные.

Если рёбра графа имеют направление, то оно отображается стрелками, а граф называется ориентированным (направленным). Например, ориентированным будет граф река с притоками. (рисунок 4 «Ориентированный граф»)

Рисунок 4 «Ориентированный граф»

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

Рисунок 5 «Неориентированный граф»

Теперь перейдём к разбору задачи № 13 из Демоверсии ЕГЭ по информатике на подсчёт путей с обязательной вершиной с помощью графа (рисунок 6 «Задание №13»).