Задача A1. Лекция. Графы. Определения ≡
Условие
Ориентированный граф (directed graph) определяется как пара множеств (V,E), где V — конечное множество, а E — множество всех пар элементов из V, т.е. подмножество множества V × V. Ориентированный граф иногда для краткости называют орграфом (digraph). Множество V называют множеством вершин графа (vertex set); его элемент называют вершиной графа (vertex; множественное число vertices). Множество E называют множеством ребер (edge set) графа; его элементы называют ребрами (edges). На рисунке 1(а) показан ориентированный граф с множеством вершин {1,2,3,4,5,6}. Вершины изображены кружками, а ребра — стрелками. Заметим, что граф может содержать ребра-петли (self-loops), соединяющие вершину с собой.
В неориентированном (undirected) графе G = (V, E) множество ребер E состоит из неупорядоченных (unordered) пар вершин: парами являются множества {u, v}, где u, v ∈ V и u ≠ v. Мы будем обозначать неориентированное ребро как (u, v) вместо {u, v}; при этом для неориентированного графа (u, v) и (v, u) обозначают одно и то же ребро. Неориентированный граф не может содержать ребер-петель, и каждое ребро состоит из двух различных вершин. На рисунке 1(б) изображен неориентированный граф с множеством вершин {1,2,3,4,5,6}.
Многие понятия параллельно определяются для ориентированных и неориентированных графов (с соответствующими изменениями). Про ребро (u, v) ориентированного графа говорят, что оно выходит из (incident from, leaves) вершины u и входит в (incident to, enters) вершину v. Например, на рис. 1(а) имеется три ребра, выходящих из вершины 2 ((2,2), (2,4), (2,5)) и два ребра, в нее входящих ((1,2), (2,2)). Про ребро (u, v) неориентированного графа говорят, что оно инцидентно вершинам (incident on vertices) u и v. Например, на рис. 1 (б) есть два ребра, инцидентные вершине 2 (ребра (1,2) и (2,5)).
Если в графе G имеется ребро (u, v), говорят, что вершина v смежна с вершиной u (is adjacent to u). Если вершина v смежна с вершиной u в ориентированном графе, пишут u→ v. Для обоих рисунков 1(а) и 1(б) вершина 2 является смежной с вершиной 1, но лишь во втором из них вершина 1 смежна с вершиной 2 (в первом случае ребро (2,1) отсутствует в графе).
Степенью (degree) вершины в неориентированном графе называется число инцидентных ей ребер. Например, для графа рис. 1(б) степень вершины 2 равна 2. Для ориентированного графа различают исходящую степень (out-degree), определяемую как число выходящих из нее ребер, и входящую степень (in-degree), определяемую как число входящих в нее ребер. Сумма исходящей и входящей степени называется степенью вершины. Например, вершина 2 в графе рис. 1(а) имеет входящую степень 2, исходящую степень 3 и степень 5.
Путь длины k (path of length k) из вершины u в вершину v определяется как последовательность вершин 〈 v0, v1, v2, ..., vk〉, в которой v0 = u, vk = v и (vi − 1, vi) ∈ E для всех i = 1,2,…,k. Этот путь содержит (contains) вершины v0, v1,...,vk и ребра (v0, v1), (v1,v2),...,(vk − 1,vk). Вершину v0 называют началом пути, вершину vk — его концом;говорят, что путь ведет из v0 в vk. Если для данных вершин u и u′ существует путь p из u в u′, то говорят, что вершина u′ достижима из u по пути p (u′ is reachable from u via p).
Циклом (cycle) в ориентированном графе называется путь, в котором начальная вершина совпадает с конечной и который содержит хотя бы одно ребро. Цикл 〈 v0, v1, ..., vk〉 называется простым, если в нем нет одинаковых вершин (кроме первой и последней), т.е. если все вершины v1, v2,...,vk различны. Ребро-петля является циклом длины 1. Мы отождествляем циклы, отличающиеся сдвигом вдоль цикла: один и тот же цикл длины k может быть представлен k различными путями (в качестве начала и конца можно взять любую из k вершин). Например, на рис. 1(а) пути 〈 1, 2, 4, 1〉, 〈 2,4,1,2〉 и 〈 4,1,2,4〉 представляют один и тот же цикл. Этот цикл является простым, в то время как цикл 〈 1,2,4,5,4,1〉 таковым не является. На том же рисунке есть цикл 〈 2,2〉, образованный единственный ребром-петлей (2,2).
В неориентированном графе путь 〈 v0, v1, ..., vk〉 называется (простым) циклом, если k ≥ 3, v0 = vk и все вершины v1, … , vk различны. Например, на рис. 1(б) имеется простой цикл 〈 1, 2, 5, 1〉.
Граф, в котором нет циклов, называется ациклическим (acyclic).
Неориентированный граф называется связным (connected), если для любой пары вершин существует путь из одной в другую. Максимальные по включению (нельзя добавить ни одной вершины, сохранив связность) связные подграфы называются связными компонентами (connected components) графа. Например, на рис. 1(б) имеется три связные компоненты: {1,2,5}, {3,6} и {4}. Неориентированный граф связен тогда и только тогда, когда он состоит из единственной связной компоненты.
Ориентированный граф называется сильно связным (strongly connected), если из любой его вершины достижима (по ориентированным путям) любая другая. Любой ориентированный граф можно разбить на сильно связные компоненты, которые определяются как максимальные по включению сильно связные подграфы. Ориентированный граф сильно связен тогда и только тогда, когда состоит из единственной сильно связной компоненты. Граф на рис. 1(а) имеет три таких компоненты: {1,2,4,5}, {3} и {6}. Заметим, что вершины {3,6} не входят в одну сильно связную компоненту, так как 3 достижима из 6, но не наоборот.
Упражнения
Покажите, что сумма степеней любого графа четна.
Покажите, что число нечетных вершин любого графа четно.
Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?
Покажите, что для любого связного неориентированного графа G = (V, E) выполняется соотношение |E| ≥ |V| − 1.
В графе G = (V, E) любая пара вершин соединена либо ребром красного цвета, либо ребром зеленого цвета. Пусть G1 — подграф графа G, состоящий только из ребер зеленого цвета и инцидентных им вершин. Пусть, аналогично, G2 — подграф, состоящий только из ребер красного цвета. Покажите, что либо G1, либо G2 является связным.
Подсказка (выделите текст, чтобы прочесть): Между любыми двумя вершинами в вышеописанном графе G существует либо полностью зеленый, либо полностью красный путь, состоящий из не более, чем двух ребер.