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

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

Графом $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 году выдающийся математик Леонард Эйлер заинтересовался этой задачей, после чего привел строгое доказательство того, что сделать это невозможно. Результаты исследования Эйлера заложили основу теории графов и отлично иллюстрируют направление её развития в настоящее время.

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

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

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

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

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

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

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

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

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

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

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

Литература

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

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

контакты

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

Биологические ориентированные графы (биоорграф) медоносной лчелы.

img src=»http://paseka-ru.narod.ru/pic/bioorgrafbee-8.png»width=»507″ height=»619″ border=»0″ alt=» Биограф пчел-8″>

Развязка узлов систем рабочей пчелы

Биологические ориентированные графы (биоорграф) в развязке общего узла графа (Ps) пищеварительной системы медоносной лчелы

Развязка узла мышечной системы биоорграф по трем отделам тела пчел.©

Статья №1. 14.02.2011

1. Графы . Графы, Орграфы, Графы связи связи и биоорграфы в моделировании с модулями и моделями особей пчел

1.1. Теория графов

Краткое представление о теории графоф из Википедии

Материал из Википедии — свободной энциклопедии. /Интернет/

Тео́рия гра́фов — раздел дискретной математике, изучающий свойства графов. В общем смысле граф представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара множеств G=(V,E), где V есть подмножество любого счётного множества, а E — подмножество V×V.

Изображение Графов с шестью вершинами (узлами) и семью рёбрами

(Все изображения смотреть в материалах из Википедии — свободной энциклопедии). /Интернет/

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

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

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории. Семь мостов Кёнигсберга — один из первых результатов в теории графов, опубликован Эйлером в 1736.

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

1.1.1. Применение теории графов

В схемотехнике (топология) межсоединений элементов на печатной плате или микросхеме представляет собой граф или гиперграф) [2].

В химии (для описания структур, путей сложных реакций[1], правило фаз также может быть интерпретировано как задача теории графов); компьютерная химия — сравнительно молодая область химии, основанная на применении теории графов. Теория графов представляет собой математическую основу хемоинформатики. Теория графов позволяет точно определить число теоретически возможных изомеров у углеводородов и других органических соединений.

Также в других облостях можно смотреть материал из Википедии — свободной энциклопедии

Также других облостях можно смотреть материал из Википедии — свободной энциклопедии

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

Материал из Википедии — свободной энциклопедии

1.2.1. Краткое представление орграф

Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках (Оре) и просто рёбрами.Формально, орграф D =( V , E ) есть множество E упорядоченных пар вершин .Дуга < u , v >инцидентна вершинам u и v . При этом говорят, что u — начальная вершина дуги, а v — конечная вершина.

Изображение орграфов с тремя узлами

(Все изображения смотреть в материалах из Википедии — свободной энциклопедии). /Интернет/

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

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

Направленный полный граф называется турниром

Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг, вида v 0 < v 0, v 1>v 1 < v 1, v 2>v 2. vn (вершины могут повторяться). Длина маршрута — количество дуг в нем.

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

Контур есть замкнутый путь.

Направленный ациклический граф или гамак есть бесконтурный орграф.

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

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

1.2.2. Применение орграфов

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

o В комбинаторике перестано́вка — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i -й элемент из набора. Число n при этом называется порядком перестановки.

В теории групп под перестановкой (подстановкой) произвольного множества подразумевается биекция этого множества на себя.\

Примечание. Более подробно о Теории Графов и Орграф в доступных материалах Википедии — свободной энциклопедии. /Интернет/

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

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

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

Этот граф состоит из 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
Олимпиадное программирование в Бресте и Беларуси


Похожие публикации:

Как зайти на протон майл в обход блокировки
Как настроить телегид на телевизоре самсунг
Как начать работать в it сфере без опыта
Как считать строку в питоне