Graph

Graph: vertices, edges. Undirected graph vs. directed graph (digraph), arcs. Origin (source) and destination (target) of an arc. Adjacent vertices, incident edge-vertex. Outgoing and incoming edges, degree of a vertex, in-degree, out-degree. Multigraph (parallel edges). Loops and self-loops. Simple graph: undirected, without parallel edges and self-loops.
Path, cycle, simple path, simple cycle.  Full graph, null graph. Connected grpahs, strongly connected and weakly connected digraphs. Subgraph and block. Free tree, forest. Spanning graph and spanning tree. Adjacency matrix, incidence matrix. Product, sum, transitive closure, reflexive transitive closure. Theorem about simple cycles. Euler cycle (Euler tour), Hamilton cycle (traveling salesman). Matrix of shortest pathlengths, matrix of weights, adjacency list structure. Representations for graph structures: graphical, edge list, matrices, pointer structures...

Traversal of an adjacency structure. Creating an adjacency matrix. Converting adjacency matrix into matrix of shortest pathlengths (matrix of distances). Floyd-Warshall algorithm.
Topological sort of an acyclic digraph. Graph traversals: depth-first and breadth-first search. Using queues. Shortest paths from a given source, Dijkstra's algorithm. Finding connected components. Special case of shortest paths. Minimal spanning tree: Kruskal's algorithm and Prim's algorithm.

Graaf


G = (V, E) - graaf

V - lõplik tippude hulk

E C V x V (tipupaaride hulga alamhulk)

Kui E elemente vaadeldakse kaheelemendiliste hulkadena (tippude järjekord paaris ei ole oluline), siis nimetatakse graafi orienteerimata graafiks ning hulka E graafi servade hulgaks.

Kui E elemente vaadeldakse järjestatud tipupaaridena, siis nimetatakse graafi orienteeritud graafiks (digraph) ning hulka E graafi kaarte hulgaks.


Graafiga seotud mõisteid

Kui hulka E vaadeldakse multihulgana (element võib hulgas esineda mitmes eksemplaris), siis nimetatakse graafi multigraafiks (kordsete servade/ kaartega graafiks).

Paari (v, v) hulgast E nim. silmuseks.

Tippe u, v hulgast V nim. serva e=(u, v) otstippudeks, samuti öeldakse, et tipud u ja v on intsidentsed servaga e (orienteerimata graafis u ja v on naabertipud).

Silmuste ja kordsete servadeta orienteerimata graafi nim. lihtgraafiks.

Graafi G = (V, 0) nim. nullgraafiks (servade hulk on tühi).

Lihtgraafi

G = (V, VxV \ {(v, v)| v kuulub hulka V})

nim. täisgraafiks (esinevad kõik erinevate tippude vahelised servad).

Tee tipust u tippu v on paarikaupa ühiste otstippudega kaarte jada:

(u, w0), (w0, w1), ... , (wn, v) kuuluvad hulka E .

Orienteerimata graafi nim. sidusaks, (orienteeritud graafi tugevalt sidusaks) kui leidub tee mistahes tipust mistahes teise tippu.

Orienteeritud graaf on nõrgalt sidus, kui kaarte suundade ärajätmisel saadav orienteerimata graaf on sidus.

Graafi G1 = (V1, E1) nim. graafi G = (V, E) alamgraafiks, kui V1 on hulga V alamhulk ja E1 on E ühisosa hulgaga V1xV1 (NB! mitte selle ühisosa alamhulk: alamhulga korral on tegemist nn. blokiga).

Külgnevusmaatriks:

|V|x|V| maatriks A=a[i, j], milles

a[i, j] = 1, kui kaar (i, j) kuulub hulka E ning a[i, j] = 0 vastupidisel juhul.

Multigraafi korral a[i, j] on tipust i tippu j viivate kaarte arv.

Graafide G1=(V, E1) ja G2=(V,E2) korrutis on graaf G=(V, E), kus

E = { (u, v) hulgast VxV | leidub w, mis kuulub hulka V nii, et:
(u, w) kuulub hulka E1 ja (w, v) kuulub hulka E2 }.

Graafide G1=(V, E1) ja G2=(V,E2) summa on graaf G=(V, E), kus E on hulkade E1 ja E2 ühend.

Graafi G transitiivne sulund G+ saadakse lähtegraafile kõigi niisuguste kaarte (u, v) lisamisega, mille korral graafis G leidub tee tipust u tippu v:

G+ = G + GG + GGG + ...

Transitiivsele sulundile kõigi silmuste lisamisel saadakse refleksiivne transitiivne sulund:

G* = G+ + {(v, v) | v kuulub hulka V}

Ahel on tee, milles servad ei kordu.

Lihtahel on ahel, milles ka tipud ei kordu.

Tsükkel on kinnine ahel (nullist suurema pikkusega ahel mingist tipust iseendasse).

Lihttsükkel on kinnine lihtahel.

Teoreem: Iga tsükkel on lihttsüklite ühend.

Tsüklit, mis läbib kõik graafi servad täpselt ühe korra, nim Euleri tsükliks, kõiki tippe täpselt üks kord läbivat tsüklit nim. Hamiltoni tsükliks.

Euleri ahel, Hamiltoni ahel - vastavad ahelad.

Kauguste maatriks D=d[i, j] on |V|x|V| maatriks, milles d[i, j] on kaare (i, j) "pikkus" (kui kaar puudub, võib pikkuseks lugeda lõpmatuse).

Analoogiliselt võib kaartega siduda kaalud - tulemuseks on nn. kaalude maatriks (puuduva kaare kaal tavaliselt null).

Tipust v lähtuvate kaarte hulka tähistame:

Adj(v) = {e hulgast E | w kuulub hulka V: e=(v,w)}


Külgnevusstruktuur on hulk

{ (v, Adj(v) ) | v kuulub hulka V }


Graafi kujutamine

1. Joonis (huvipakkuv probleem selles valdkonnas - tasandilised graafid).

2. Kaarte loetelu (eeldades, et otstippude kohta käiv informatsioon on kaares olemas).

Sellise loetelu organiseerimiseks on palju võimalusi.

3. Külgnevusmaatriks (kaaslusmaatriks) jt. graafi ühest taastamist võimaldavad maatriksid.

4. Külgnevusstruktuur - tippude loetelu, milles iga tipuga on seotud sellest lähtuvate kaarte loetelu (iga kaare kohta on teada tipp, kuhu ta suubub).


Graafi kujutamine külgnevusstruktuuri abil

Näide

Mälupilt


E={ (A,B), (A,C), (A,D), (B,C), (C,D) }

Graafi töötlemine

Külgnevusstruktuuri läbivaatus

Näide: külgnevusstruktuuri trükk

   /**
    * Creates textual representation for the graph.
    */
   public String toString() { 
      StringBuffer result = new StringBuffer ("");
      String nl = System.getProperty ("line.separator");
      result.append (nl + "Graph: " + getId().toString());
      Iterator vertIt = vertices();
      while (vertIt.hasNext()) {
	 Vertex vert = (Vertex)vertIt.next();
	 result.append (nl + vert.toString());
	 result.append (" --> ");
	 Iterator outeIt = vert.outEdges();
	 while (outeIt.hasNext()) {
            Edge e = (Edge)outeIt.next();
	    Vertex v2 = e.getToVert();
	    result.append (v2.toString() + " ");
	    result.append ( "(" + e.toString());
	    result.append ( ") " );
         }
      }
      result.append (nl);
      return result.toString();
   }

Külgnevusmaatriksi ehitamine



   /**
    * Builds the matrix for a given graph.
    * @param g graph
    * @return adjacency matrix 
    */
   public static AdjMatrix getAdjMatrix (Graph g) {
      int n = 0;
      Iterator vit = g.vertices();
      while (vit.hasNext()) {
         n++;
         Vertex v = (Vertex)vit.next();
         v.setVInfo (n);
      }
      AdjMatrix result = new AdjMatrix (2*n + 1); // double size!!!
      result.setNvert (n);
      Iterator eit = g.edges();
      while (eit.hasNext()) {
         Edge e = (Edge)eit.next();
         int i = e.getFromVert().getVInfo() - 1;
         int j = e.getToVert().getVInfo() - 1;
         result.set (i, j, result.get (i, j)+1);
      }
      return result;
   }

Kauguste arvutamine

Ülesanne: arvutada etteantud külgnevusmaatriksi järgi lühimad teepikkused kõigi tipupaaride vahel (nn. "kauguste maatriks").

Elimineerida arvutustest kordsed kaared ja silmused.

Lugeda iga järelejäänud kaare pikkuseks 1 ühik, kaare puudumine tähistada pikkusega "lõpmatus".

Floyd-Warshalli algoritm

   /**
    * Converts adjacency matrix to the matrix of distances.
    * @param mat adjacency matrix
    * @return matrix of distances, where each edge has length 1
    */
   public static DistMatrix getDistMatrix (AdjMatrix mat) {
      int nvert = mat.getNvert();
      DistMatrix result = new DistMatrix (nvert);
      result.setNvert (nvert);
      if (nvert < 1) return result;
      int INFINITY = 2*nvert + 1; // Integer.MAX_VALUE / 2; // NB!!!
      for (int i=0; i<nvert; i++) {
         for (int j=0; j<nvert; j++) {
            if (mat.get (i, j) == 0) {
               result.set (i, j, INFINITY);
            } else {
               result.set (i, j, 1);
            }
         }
      }
      for (int i=0; i<nvert; i++) {
         result.set (i, i, 0);
      }
      return result;
   }

   /**
    * Calculates shortest paths using Floyd-Warshall algorithm.
    * This matrix will contain shortest paths between each pair of vertices.
    */
   public void shortestPaths() {
      int n = getNvert(); // number of vertices
      if (n < 1) return;
      for (int k=0; k<n; k++) {
         for (int i=0; i<n; i++) {
            for (int j=0; j<n; j++) {
               int newlength = get (i, k) + get (k, j);
	       if (get (i, j) > newlength) {
                  set (i, j, newlength); // new path is shorter
               }
            }
         }
      }
   }

Atsüklilise orienteeritud graafi tippude topoloogiline sorteerimine:

Leida tippude niisugune järjestus < , et mistahes kaare i -> j korral kehtiks i < j (kaartega määratud osalise järjestuse "pakkimine" lineaarse järjestuse sisse).

Näide
Topoloogiline sorteerimine

   /**
    * Topological sort of vertices.
    * For each vertex vInfo=0 if the graph cannot be sorted,
    * otherwise vInfo is the ordinal number of the vertex.
    */
   public void topolSort() {
      boolean cycleFound = false;
      List order = Collections.synchronizedList (new LinkedList());
      setGInfo (0); // count number of vertices
      Iterator vit = vertices();
      while (vit.hasNext()) {
         ((Vertex)vit.next()).setVInfo (0);
	 setGInfo (getGInfo() + 1);
      }
      Iterator eit = edges();
      while (eit.hasNext()) {
         Edge e = (Edge)eit.next();
	 Vertex v = e.getToVert();
	 // count number of incoming edges
	 v.setVInfo (v.getVInfo() + 1);
      }
      List start = Collections.synchronizedList (new LinkedList());
      vit = vertices();
      while (vit.hasNext()) {
         Vertex v = (Vertex)vit.next();
	 if (v.getVInfo() == 0) {
            start.add (v); // no incoming edges
         }
      }
      if (start.size() == 0) cycleFound = true;
      while ((!cycleFound)&(start.size() != 0)) {
         Vertex current = (Vertex)start.remove (0); // first vertex
	 order.add (current);
	 eit = current.outEdges(); // "remove" outgoing edges
	 while (eit.hasNext()) {
            Edge e = (Edge)eit.next();
	    Vertex v = e.getToVert();
	    v.setVInfo (v.getVInfo() - 1);
	    if (v.getVInfo() == 0) {
               start.add (v); // no incoming edges anymore
            }
         }
      }
      if (getGInfo() != order.size()) cycleFound = true;
      if (cycleFound) {
         Iterator it = vertices();
	 while (it.hasNext()) {
            Vertex v = (Vertex)it.next();
	    v.setVInfo (0);
         }
      } else {
         int i = 0;
	 Iterator it = order.iterator();
	 while (it.hasNext()) {
            i++;
	    Vertex v = (Vertex)it.next();
	    v.setVInfo (i);
         }
      }
      setGInfo (0);
      return;
   } // end of topolSort()

Graafi läbimine

Üldjuht

Tipud võivad olla "valged" (töötlemata), "hallid" (järjekorras) või "mustad" (töödeldud).
Algselt on kõik tipud valged ja järjekord tühi.
Läbimine algab mingist tipust t: t lisatakse järjekorda ning värvitakse halliks.
Järgnevat tsüklit täidetakse niikaua, kuni järjekord pole tühi:
järjekorrast eemaldatakse tipp v,
v töödeldakse,
v värvitakse mustaks,
vaadatakse läbi kõik v vahetud järglased w:
kui w on valge, siis w lisatakse järjekorda ning värvitakse halliks.

Läbimine laiuti

Eelmises algoritmis esinev tippude töötlemise järjekord on FIFO

Läbimine sügavuti

Eelmises algoritmis esinev järjekord on LIFO (magasin)

Näide
Ülesandele spetsiifiline läbimine - näit. nn. Dijkstra algoritmis lühimate teede leidmiseks antud tipust . Järjekord on muutuvate eelistustega järjekord.

Läbimine laiuti

   /**
    * Traverse the graph breadth-first.
    * Execute vertWork (v) for each vertex v.
    * @param s source vertex
    */
   public void breadthFirst (Vertex s) {
      if (getVertexList() == null) return;
      if ((!getVertexList().contains (s))|(s.getGraph() != this))
         throw new RuntimeException ("wrong argument to traverse!!");
      Iterator vit = vertices();
      while (vit.hasNext()) {
         Vertex v = (Vertex)vit.next();
         v.setVInfo (0); // "white"
      }
      List vq = Collections.synchronizedList (new LinkedList());
      vq.add (s);
      s.setVInfo (1); // "gray"
      while (vq.size() > 0) {
         Vertex v = (Vertex)vq.remove (0); // breadth == FIFO
         vertWork (v);
         v.setVInfo (2); // "black"
         Iterator eit = v.outEdges();
         while (eit.hasNext()) {
            Edge e = (Edge)eit.next();
            Vertex w = e.getToVert();
            if (w.getVInfo() == 0) {
               vq.add (w);
               w.setVInfo (1);
            }
         }
      }
   }

   /** Work to do when traversing the graph */
   public void vertWork (Vertex v) {
      System.out.print (" " + v.toString());
   }

Lähtetipp (allikas) olgu s. Leiame lühimad teed tipust s kõigisse saavutatavatesse tippudesse (Dijkstra algoritm).

Näide.

   /**
    * Shortest paths from a given vertex. Uses Dijkstra's algorithm.
    * For each vertex vInfo is length of shortest path from given
    * source s and vObject is previous vertex from s to this vertex.
    * @param s source vertex
    */
   public void shortestPathsFrom (Vertex s) {
      if (getVertexList() == null) return;
      if ((!getVertexList().contains (s)) | (s.getGraph() != this))
         throw new RuntimeException ("wrong argument to Dijkstra!!");
      int INFINITY = Integer.MAX_VALUE / 4; // big enough!!!
      Iterator vit = vertices();
      while (vit.hasNext()) {
         Vertex v = (Vertex)vit.next();
         v.setVInfo (INFINITY);
         v.setVObject (null);
      }
      s.setVInfo (0);
      List vq = Collections.synchronizedList (new LinkedList());
      vq.add (s);
      while (vq.size() > 0) {
         int minLen = INFINITY;
         Vertex minVert = null;
         Iterator it = vq.iterator();
         while (it.hasNext()) {
            Vertex v = (Vertex)it.next();
            if (v.getVInfo() < minLen) {
               minVert = v;
               minLen = v.getVInfo();
            }
         }
         if (minVert == null) 
            throw new RuntimeException ("error in Dijkstra!!");
         if (vq.remove (minVert)) {
            // minimal element removed from vq
         } else
            throw new RuntimeException ("error in Dijkstra!!");
         it = minVert.outEdges();
         while (it.hasNext()) {
            Edge e = (Edge)it.next();
            int newLen = minLen + e.getEInfo();
            Vertex to = e.getToVert();
            if (to.getVInfo() == INFINITY) {
               vq.add (to);
            }
            if (newLen < to.getVInfo()) {
               to.setVInfo (newLen);
               to.setVObject (minVert);
            }
         }
      }
   } // end of shortestPathsFrom()


Sidususkomponentide leidmine

Leida iga tipu v sidususkomponendi järjekorranumber k(v).
Algselt kõigis tippudes k(v) = 0.
Vaadeldava sidususkomponendi järjekorranumber n = 0.
Tsükkel üle kõigi tippude v (kasutades külgnevusstruktuuri):

kui k(v)==0, siis n=n+1 ning nummerdada kõik v-st saavutatavad tipud w numbriga n:
k(w)=n.
   /**
    * Enumerate connected components of this undirected graph.
    * For each vertex vInfo is the number of connected component.
    */
   public void connectedComponents() {
      Iterator<Vertex> vit = vertices();
      while (vit.hasNext()) {
         Vertex v = vit.next();
         v.setVInfo (0);
      }
      int n = 0; // number of component
      vit = vertices();
      while (vit.hasNext()) {
         Vertex v = vit.next();
         if (v.getVInfo() == 0) {
            n++;
            enumerate (v, n);
         }
      }
   }

   /**
    * Enumerate all reachable vertices with given number.
    * @param v source vertex
    * @param n number
    */
   void enumerate (Vertex v, int n) {
      v.setVInfo (n);
      Iterator<Edge> eit = v.outEdges();
      while (eit.hasNext()) {
         Edge e = eit.next();
         Vertex w = e.getToVert();
         if (w.getVInfo() == 0) {
            enumerate (w, n);
         } else;
      }
   }

Lühimate teede leidmine graafis

Lühimad teepikkused kõigi tipupaaride vahel: Floyd-Warshalli algoritm - O(|V|3)

Lähtudes antud tipust: Dijkstra algoritm - O(|V|log|V| + |E|)


Otseteede leidmine

Leida minimaalse kaarte arvuga tee antud tipust kõigisse teistesse tippudesse.

Lühimate teede ülesande erijuht (kõikide kaarte kaalud võrdsed)

Graafi läbimine laiuti, kus järjekorrast (FIFO) võetud tipu v järglased w seotakse ahelasse:

eellane(w) = v

Kaarte arvu minimaalsuse tagab läbimise järjekord

(Miks?)

Võrrelda Dijkstra algoritmiga

Toesepuu

    Sidusa lihtgraafi (V, E) toesepuuks e. toeseks (spanning tree) nim. sidusat atsüklilist graafi (V, T), milles T on E alamhulk.

Kõik tipud on samad, servi on eemaldatud nii, et kaoksid tsüklid, aga sidusus säiliks. Toes ei ole üldjuhul üheselt määratud.

Kui servadel on mittenegatiivsed kaalud, siis pakub huvi niisuguse toese leidmine, mille kogukaal oleks minimaalne (kõigi toespuude hulgast).

Kruskali algoritm: järjestada servad kaalude järgi mittekahanevalt ning valida selle alusel järjekordne serv toesesse juba olemasolevate osapuude ühendamiseks (kui moodustub tsükkel, siis seda serva ei võeta). Alt-üles (alguses on üksikud tipud, lõpuks peavad kõik tipud esinema omas sidususkomponendis), ahne strateegia (valitakse hetkel parim tee).

Primi algoritm: töötatakse antud lähtetipust laiuti sarnaselt Dijkstra algoritmiga (toesesse valitakse hetkejätkudest minimaalse kaaluga serv, meeles peetakse kaalu ja eellast, vajadusel parandatakse eellast teel allikast antud tipuni).



Jaanus Pöial