Основные модели

Под графом мы будем понимать пару множеств \(V\) и \(E\) и пару отображений \(s,t:E\to V\). Традиционные названия:

• элементы \(V\) называются вершинами
• элементы \(E\) называются рёбрами
• отображение \(s\) называется начало ребра
• отображение \(v\) называется конец ребра

Для многих приложений информация о «направлении» рёбер избыточна. В таких ситуациях вместо отображений \(s\) и \(t\) достаточно одно отображение \(v:E\to \mathrm{P}V\), сопоставляющее каждому ребру одно- или двухэлементное подмножество множества \(V\). Соответствующий математический объект называется неориентированным графом.

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

Небольшое предисловие

Далее многие понятия и алгоритмы пояснены программным кодом. Весь программный код приведён на языке Python, если не оговорено иное.

Небольшая шпаргалка по Python доступна здесь. За всем остальным рекомендуется обращаться на официальный сайт или на informatics.

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

Подраздел «упражнения» в конце каждого раздела следует рассматривать как (обязательное) домашнее задание. После раздела с упражнениями идёт раздел с (необязательными) задачами повышенной сложности: их выполнение может потребовать значительных затрат времени (но при этом может дать какой-то новый взгляд на рассматриваемый материал).

Предостережение о деревьях

В математике деревом называется связный неориентированный граф без циклов. В информатике деревьями обычно называют другой вид данных, традиционно называемый в математике словом «формула».

А именно, (непустым) деревом называется единица данных, спаренная с последовательностью деревьев (обратите внимание на рекурсию в определении!).

Например, формальным представлением формулы \((2+3\cdot 4)/5\) может являться программа

('/', [
  ('+', [
    (2,[]),
    ('*', [
      (3, []), 
      (4, [])
    ])
  ]),
  (5,[])
])

На этом разговор о деревьях мы (временно) закончим.

Наивная модель

Наиболее простой способ моделировать граф — списком его рёбер. Например, так:

[
  ('A', (1,3)), 
  ('B', (1,4)), 
  ('C', (2,4)),
  ('D', (1,3)),
]

Такая модель неявно предполагает, что множество вершин содержит числа 1, 2, 3 и 4.

Подобным образом можно моделировать и неориентированный граф:

[
  ('A', {1,3}), 
  ('B', {1,4}), 
  ('C', {2,4}),
  ('D', {1,3}),
]

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

Оказывается, можно обойтись существенно меньшими ресурсами.

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

Научимся сначала отвечать на вопрос «какие рёбра соединяют такую-то пару вершин?».

Для этого можно построить отображение вида

def edges_of_vertices(v1, v2):
  if (v1,v2) == (1,3): return ['A','D']
  if (v1,v2) == (1,4): return ['B']
  if (v1,v2) == (2,4): return ['C']
  return []

Само по себе оно ничем не лучше списка рёбер. Но далее можно воспользоваться эквивалентностью множеств \(A\times B\to C\) и \(A\to(B\to C)\):

# отображение edges_of_vertices2 построено так, чтобы выполнялось
# edges_of_vertices2(v1)(v2) == edges_of_vertices(v1,v2)
def edges_of_vertices2(v1):
  def f1(v2):
    if v2 == 3: return ['A','D']
    if v2 == 4: return ['B']
    return []

  def f2(v2):
    if v2 == 4: return ['C']
    return []

  def f(v2): return []

  if v1 == 1: return f1
  if v1 == 2: return f2
  return f

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

graph_table = [
  [[], [], [], [],        []],
  [[], [], [], ['A','D'], ['B']],
  [[], [], [], [],        ['C']],
  [[], [], [], [],        []],
  [[], [], [], [],        []],
]

Теперь выражение edges_of_vertices(v1,v2) почти эквивалентно выражению graph_table[v1][v2]. Почти — поскольку при некорректных v1 и v2 первое выражение равно пустому списку, а второе в процессе вычисления выдаёт ошибку.

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

Плотные и разреженные матрицы

У вышеприведённого подхода есть несколько недостатков:

• требуется каким-то образом сопоставлять вершинам целые числа (причём желательно — в непрерывном диапазоне от 0 до чего-нибудь)
• занимаемая матрицей смежности память пропорциональна квадрату количества вершин
• матрица смежности требует некоторых модификаций для быстрого ответа на вопрос о соседях заданной вершины (например, можно хранить ответ на этот вопрос прямо в ней по какому-нибудь незанятому индексу внутреннего массива)

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

В остальных случаях рекомендуется пользоваться разреженной матрицей смежности, которую можно эффективно реализовать при помощи ассоциативных массивов:

graph_sparse_table = {
  1: {3: ['A', 'D'], 
      4: ['B']},

  2: {4: ['C']},
}

Упражнения

Упражнения нужно сдавать одним файлом мне на почту (arbrk1@gmail.com). В каждом упражнении требуется написать одну или несколько функций.

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

Всё же, каков ответ на те два вопроса?

Для разреженной матрицы можно написать функции

def edges_of_vertices(g, v1, v2):
  if not (v1 in g): return []
  if not (v2 in g[v1]): return []
  return g[v1][v2]

def neighbors(g, v):
  if not (v in g): return []
  
  return [n for n in g[v]]

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

Очень плотная матрица смежности

Очень плотная матрица смежности получается из матрицы смежности плотной упаковкой внутренних массивов:

def pack(g):
  vertex_count = len(g)
  return (vertex_count, [x for row in g for x in row])

Напишите функции packed_edges_of_vertices и packed_neighbors, работающие с очень плотными матрицами смежности.

Обратите внимание на то, что решение вида:

def unpack(g):
  n,m = g

  return  [m[i*n : (i+1)*n] for i in range(n)]

def packed_edges_of_vertices(g, v1, v2):
  return edges_of_vertices(unpack(g), v1, v2)

def packed_neighbors(g, v):
  return neighbors(unpack(g), v)

не принимается: время его работы пропорционально квадрату количества вершин. Должно же быть (с точностью до постоянного множителя) не больше, чем у обычных edges_of_vertices и neighbors соответственно.

Задачи повышенной сложности

Текст по дереву

Напишите функцию text_of_tree, восстанавливающую (текстовую) формулу по соответствующему дереву. Например,

text_of_tree(('/', [('+', [(2,[]),('*', [(3, []), (4, [])])]),(5,[])]))

должно выдавать что-то наподобие

"(2 + (3 * 4)) / 5"

Допускается другая расстановка скобок.

Дерево по тексту

Напишите функцию tree_of_text, строящую дерево по текстовому представлению формулы. Для простоты можно считать, что в тексте допускаются только скобки, пробелы, числа и знак +.

Помните, что если скобок не хватает, то они ставятся традиционным образом:

tree_of_text("1+2+3") == ( '+', [ ( '+', [ (1,[]), (2,[]) ] ), (3,[]) ] )