Графы

Граф (graph) обычно определяется как множество точек (называемых вершинами (vertices)) вместе с набором линий (называемых ребрами (edges)), которые соединяют определенные пары вершин. Каждая пара вершин соединяется не более чем одним ребром. Две вершины называются смежными (adjacent), если их соединяет ребро. Если \(V\) и \(\acute{V}\) являются вершинами и \(n \geq 0\), то \((V_{0}, V_{1}, ... , V_{n})\) называется путем длины n от вершины \(V\) к вершине \(\acute{V}\), если \(V = V_{0}\), вершина \(V_{k}\) является смежной для вершины \(V_{k+1}\) для \(0 \leq k < n\), а \(V_{n} = \acute{V}\). Путь называется простым (simple), если различны вершины \(V_{0}, V_{1}, ... , V_{n−1}\) и если различны вершины \(V_{1}, ... , V_{n−1}, V_{n}\). Граф называется связным (connected), если существует путь между любыми двумя его вершинами. Циклом называется простой путь длиной, большей или равной трем, от некоторой вершины к ней самой.

Код:

В следующем коде определены классы Vertex

, Edge и Graph, которые представляют собой неориентированный граф.

Метод addVertex добавляет новую вершину в граф. Если вершина с таким же значением уже существует, то возвращает текущий граф. Если вершины с таким значением нет, то создает новую вершину и добавляет ее в граф.
Метод addEdge добавляет новое ребро в граф. Он проверяет, существуют ли исходная и конечная вершины в графе. Если хотя бы одна из вершин не найдена, то возвращает соответствующую ошибку. Если обе вершины найдены, то проверяет, существует ли уже ребро между этими вершинами. Если ребро уже существует, то возвращает соответствующую ошибку. Если ребра не существует, то создает новое ребро и добавляет его в граф.
Метод areAdjacent проверяет, являются ли две вершины смежными (т.е., имеют ли между собой ребро). Если хотя бы одна из вершин не найдена, то возвращает соответствующую ошибку. Если обе вершины найдены, то проверяет, существует ли ребро между этими вершинами, и возвращает результат.
Методы findVertexes, findVertex, findEdge служат для поиска вершин и ребер в графе.

final case class Vertex[A: Ordering](id: UUID, value: A):
  def contains(value: A): Boolean = summon[Ordering[A]].equiv(this.value, value)

final case class Edge[A](from: UUID, to: UUID, value: A)

final case class Graph[A: Ordering, B] private (
    vertices: Map[UUID, Vertex[A]],
    edges: Vector[Edge[B]]
):
  self =>

  def addVertex(value: A): Graph[A, B] =
    if vertices.exists(_._2.contains(value)) then self
    else
      val newVertex = Vertex(UUID.randomUUID(), value)
      Graph(vertices + (newVertex.id -> newVertex), edges)

  def addEdge(from: A, to: A, value: B): Either[String, Graph[A, B]] =
    for
      (fromVertex, toVertex) <- findVertexes(from, to)
      edge <- if findEdge(fromVertex.id, toVertex.id).isDefined then
        Left("Эта вершина уже содержится в графе")
      else Right(Edge(fromVertex.id, toVertex.id, value))
    yield Graph(vertices, edges :+ edge)

  def areAdjacent(from: A, to: A): Either[String, Boolean] =
    findVertexes(from, to).map(vs => findEdge(vs._1.id, vs._2.id).isDefined)

  private def findVertexes(
      from: A,
      to: A
  ): Either[String, (Vertex[A], Vertex[A])] =
    for
      fromVertex <- findVertex(from).toRight("Исходящая вершина не найдена")
      toVertex   <- findVertex(to).toRight("Конечная вершина не найдена")
    yield (fromVertex, toVertex)

  private def findVertex(value: A): Option[Vertex[A]] =
    vertices.collectFirst {
      case (id, vertex) if vertex.contains(value) => vertex
    }

  private def findEdge(from: UUID, to: UUID): Option[Edge[B]] =
    edges.find: edge =>
      edge.from == from && edge.to == to ||
        edge.from == to && edge.to == from

end Graph

Свободное дерево

Свободное дерево (free tree), или дерево без корня, определяется как связный граф без циклов.

Теорема

Если G — граф, то для него будут эквивалентными следующие утверждения.

a) G — свободное дерево.
b) G — связный граф, который при удалении произвольного ребра перестает быть связным.
c) Если \(V\) и \(\acute{V}\) — различные вершины графа G, то существует единственный простой путь от вершины \(V\) к вершине \(\acute{V}\). Более того, если граф G конечен и содержит в точности n > 0 вершин, следующие утверждения также будут эквивалентны утверждениям (a)–(c).
d) G не содержит циклов и имеет n − 1 ребер.
e) G — связный граф, который имеет n − 1 ребер.

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

Формально определим ориентированный граф (directed graph или digraph) как множество вершин и множество дуг или ребер (arcs), каждая из которых проходит от вершины \(V\) до вершины \(\acute{V}\). Если e является дугой от вершины \(V\) до вершины \(\acute{V}\), назовем V начальной (initial) вершиной дуги e, а \(\acute{V}\) — конечной (final) вершиной и запишем \(V = init(e)\), \(\acute{V} = fin(e)\). При этом возможен случай, когда \(init(e) = fin(e)\) (хотя при определении ребра обычного графа он исключается) и несколько различных дуг могут иметь одинаковые начальные и конечные вершины. Степенью выхода (outdegree) вершины \(V\) является количество дуг, которые выходят из нее, а именно — число таких дуг e, что \(init(e) = V\). Аналогично степень входа (in-degree) вершины \(V\) определяется как количество дуг, для которых \(fin(e) = V\).

Если \(e_{1}, e_{2}, ... , e_{n}\) являются дугами (с \(n \geq 1\)), то будем считать, что (\(e_{1}, e_{2}, ... , e_{n}\)) является ориентированным путем (oriented path) длины n от вершины \(V\) до вершины \(\acute{V}\), если \(V = init(e_{1}), \acute{V} = fin(e_{n})\), а \(fin(e_{k}) = init(e_{k+1})\) для \(1 \leq k < n\). Ориентированный путь (\(e_{1}, e_{2}, ... , e_{n}\)) называется простым (simple), если \(init(e_{1}), ... , init(e{n})\) различны и \(fin(e_{1}), ... , fin(e_{n})\) различны. Ориентированный цикл (oriented cycle) — это простой ориентированный путь от некоторой вершины до нее самой.

Ориентированный граф называется строго связным (strongly connected), если существует ориентированный путь от вершины \(V\) до вершины \(\acute{V}\) для любых двух вершин \(V \neq \acute{V}\). Он является корневым (rooted), если существует хотя бы один корень (root), т.е. по крайней мере одна такая вершина \(R\), при наличии которой существует ориентированный путь от \(V\) к \(R\) для всех \(V \neq R\). "Строго связный" граф всегда является "корневым", но обратное утверждение не верно.

Ориентированное дерево

Ориентированное дерево (oriented tree), иногда называемое корневым деревом, представляет собой ориентированный граф с такой вершиной \(R\), что:

a) каждая вершина \(V \neq R\) является начальной вершиной в точности одной дуги, которая обозначается как \(e[V]\);
b) \(R\) не является начальной вершиной ни одной из дуг;
c) \(R\) является корнем в указанном выше смысле (т.е. для каждой вершины \(V \neq R\) существует ориентированный путь от \(V\) к \(R\)).

Сбалансированный ориентированный граф

Цепью Эйлера (Eulerian circuit) в ориентированном графе является такой ориентированный путь \((e_{1}, e_{2}, ... , e_{m})\), что каждая дуга ориентированного графа встречается в этом пути только один раз и \(fin(e_{m}) = init(e_{1})\). Она представляет собой "полный обход" дуг диграфа.

Ориентированный граф называется сбалансированным (balanced), если каждая вершина V имеет равные по величине степени входа и выхода, т.е. сколько существует ребер, для которых вершина V является начальной, столько же существует ребер, для которых вершина V является конечной. Если ориентированный граф имеет цепь Эйлера, то очевидно, что он должен быть связным и сбалансированным, за исключением случаев, когда он имеет изолированные вершины (isolated vertices), т.е. вершины c равными нулю степенями входа и выхода.

Теоремы

Теорема Гуда

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

Ссылки:

Donald E. Knuth - The Art of Computer Programming, section 2.3.4.1 - 2.3.4.2

scalabook