Блог Scala Функ. программирование Классы типов Алгоритмы Библиотеки Упражнения Ресурсы

Графы

Граф (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, которые представляют собой неориентированный граф.

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 — граф, то для него будут эквивалентными следующие утверждения.

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

Формально определим ориентированный граф (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\), что:

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

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

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

Теоремы

Теорема Гуда

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

Ссылки: