Graf

Graf K₅

Grafem nazýváme uspořádanou trojici uzlů, hran a incidencí. Zobrazení incidence přiřazuje dvojici uzlů právě jednu hranu.

Neorientovaný graf

V případě, kdy incidence přiřazuje hraně neuspořádanou dvojici uzlů, nazýváme graf neorientovaným grafem.

Neorientovaný graf, který neobsahuje rovnoběžné hrany, nazýváme prostým grafem, v opačném případě multigrafem. V případě neexistence smyček (hrana z uzlu X zpět do uzlu X) se jedná o prostý graf bez smyček (obyčejný graf).

Speciálními případy grafu jsou diskrétní grafy, které neobsahují žádné hrany (pouze izolované uzly), prázdný graf neosahující žádné uzly a úplný obyčejný graf (K_x), jenž obsahuje $\\left( \\begin{array}{c} U\\\\ 2 \\end{array} \\right)$ hran a U uzlů (mezi každými dvěma uzly existuje hrana).

Stupeň uzlu grafu ( $\\delta$ ) je počet hran incidujících s daným uzlem. Součet stupňů uzlů je roven dvojnásobku počtu hran.

$\\sum_{u \\in U} \\delta(u) = 2 \\vert H \\vert$

Orientovaný graf

V případě zavedení orientace hran, kdy incidence přiřazuje hranám uspořádané dvojice uzlů, se jedná o orientovaný graf. Analogicky s neorientovaným grafem mluvíme o orientovaném multigrafu a prostém orientovaném grafu.

Stupeň uzlu orientovaného grafu je definovám jako součet počtu výstupních ( $\\delta ^{+}(u)$ ) a vstupních hran ( $\\delta ^{-}(u)$ ) tohoto uzlu. Součet vstupních a výstupních stupňů uzlů je roven dvojnásobku počtu hran.

$\\sum_{u \\in U} \\delta ^{+}(u) + \\sum_{u \\in U} \\delta ^{-}(u) = 2 \\vert H \\vert$

Tah, sled, cesta, souvislost

Libovolnou posloupnost uzlů a hran s nimi incidujících $\\langle u,\\; h_{1},\\; u_{2},\\; h_{2},\\; \\cdots,\\; h_{n},\\; v \\rangle$ nazýváme sledem grafu. Uzly u a v jsou krajní uzly sledu S. Délkou sledu je počet obsažených hran a značí se d(S) . Za předpokladu, že uzly u a v jsou totožné, hovoříme o uzavřeném sledu. Všechny ostatní sledy jsou otevřené, včetně sledu nulové délky.

Tah grafu je takový sled, že jsou všechny jeho hrany různé. Cesta grafu je takový tah, ve kterém každý jeho uzel inciduje s nejvýše dvěma hranami. Kružnice grafu je uzavřená cesta.

Souvislým grafem je takový neorientovaný graf, mezi jehož libovolnými uzly existuje sled. Komponenta grafu je maximální souvislý podgraf. Analogicky pro orientovaný graf hovoříme o silně souvislém grafu a silné komponentě.

Planarita grafu

Planární graf obsahující 4 stěny

Řekneme, že graf je plární právě tehdy, když lze sestrojit jeho diagram v rovině takovým způsobem, že žádné dvě hrany nemají kromě svých krajních uzlů žádné společné body. Maximální planární graf je takový graf, jehož planarita se poruší přidáním libovolné další hrany.

Diagram planárního grafu rozčleňuje rovinu do několika disjunktních oblastí, které budeme nazývat stěnami planárního grafu. Za vnější stěnu uznačíme tu, která je neomezená.

Dle Kuratowského věty je graf planární právě tehdy, neobsahuje-li podgraf homeomorfní s některým ze základních grafů $K_{5}$ , $K_{3, 3}$ . Homeomorfní jsou takové grafy, které jsou buď izomorfní, nebo je-li možné izomorfismu těchto grafů dosáhnout pomocí konečné počtu operací půlení hran v těchto grafech.

V planárním grafu platí Eulerova formule:

$\\vert H \\vert - \\vert U \\vert + 2 = r$

kde r je počet stěn (včetně vnější).

Dále platí:

$\\vert H \\vert \\leq 3\\vert U \\vert - 6$

Za předpokladu, že graf neobsahuje trojúhelníky, pak:

$\\vert H \\vert \\leq 2\\vert U \\vert - 4$

Nezávislost grafu

Podmnožina uzlů grafu G je nezávislá právě tehdy, když žádné dva z jejích uzlů neincidují s stejnou hranou $E \\in Edges(G)$ . Číslo, které označuje počet uzlů maximální nezávislé podmnožiny nazýváme nezávislostí grafu.

Barevnost grafu

Barvení grafu je úloha, při které se jednotlivým uzlům přiřazují barvy tak, že žádná hrana neinciduje s dvěma stejně barevnými uzly. Graf, který lze obarvit minimálně k barvami nazýváme k-barevným (k-chromatickým), kde k je chromatické číslo.

Protože jednotlivé barvy tvoří nezávislé podmnožiny, lze tento problém chápat jako hledání nejnižšího počtu nezávislých podmnožin, které pokryjí všechny uzly grafu.

Vrcholové pokrytí grafu

Vrcholové pokrytí (dominující podmnožina grafu) je taková podmnožina uzlů $D \\subseteq U$ , že každá hrana grafu má alespoň jeden krajní uzel v . Počet uzlů minimální dominující podmnožiny nazýváme dominancí grafu.

Klika grafu

Klika grafu je každý maximální úplný podgraf grafu G (tj. každý úplný podgraf pro který platí, že žádný z jeho nadgrafů není úplný). Maximální číslo K, pro které existuje v G klika o K vrcholech nazýváme klikovostí grafu.

Pokud v grafu G existuje klika velikosti n, pak v opačném grafu $G^{op}$ existuje nezávislá množina velikosti n.

Reprezentace grafu

Orientovaný graf

Graf se dá reprezentovat mnoha způsoby. Nelze říci, který je lepší, protože se každá reprezentace hodí k trochu jinému typu úloh. Nejčastěji je ale graf reprezentován maticí incidence, maticí sousednosti nebo pomocí spojové reprezentace.

Matice sousednosti

Matice sousednosti je matice $U \\times U$ , ve které je souřadnice daná řádkem m a sloupcem n jednotková právě tehdy když z uzlu m vede hrana do uzlu n, v opačném případě je nulová. Matice sousednosti je pro neorietované grafy symetrická podle diagonály.

$\\begin{pmatrix} & \\textcolor{red}{1} & \\textcolor{red}{2} & \\textcolor{red}{3} & \\textcolor{red}{4} \\\\ \\textcolor{red}{1} & 0 & 1 & 1 & 1 \\\\ \\textcolor{red}{2} &0 & 0 & 0 & 0 \\\\ \\textcolor{red}{3} &0 & 0 & 0 & 1 \\\\ \\textcolor{red}{4} &0 & 1 & 0 & 0 \\end{pmatrix}$

Matice incidence

Řádky matice incidence reprezentují uzly grafu, sloupce jednotlivé hrany. Souřadnice daná řádkem m a sloupcem n je 1, pokud je uzel m zdrojovým uzlem hrany n, -1 v případě, že je uzel cílovým uzlem hrany n a 0 v případě, že uzel m s hranou neinciduje.

$\\begin{pmatrix} & \\textcolor{red}{a} & \\textcolor{red}{b} & \\textcolor{red}{c} & \\textcolor{red}{d} & \\textcolor{red}{e} \\\\ \\textcolor{red}{1} & 1 & 1 & 0 & 1 & 0 \\\\ \\textcolor{red}{2} & -1 & 0 & 0 & 0 & -1\\\\ \\textcolor{red}{3} & 0 & -1 & 1 & 0 & 0\\\\ \\textcolor{red}{4} & 0 & 0 & -1 & -1 & 1 \\end{pmatrix}$

Spojová reprezentace

Spojová reprezentace je patrně nejpoužívanějším způsobem reprezentace grafu. Má-li graf m uzlů, pak spojová reprezentace obsahuje m spojových seznamů. Každý z těchto seznamů obsahuje ukazatele na všechny uzly, do kterých vede hrana z uzlu m.

$1 \\rightarrow 2,\\; 3,\\; 4$
$2 \\rightarrow null$
$3 \\rightarrow 4$
$4 \\rightarrow 2$

 /**
  * Orientovany graf (spojova reprezentace)
  * Povoluje paralelni hrany a smycky
  * @author Pavel Micka
 
  * @param <ENTITY> typ objektu ukladaneho jako data
  */
 public class LinkedGraph<ENTITY> implements GraphIface {
     /*
      * Klasicka spojova reprezentace grafu, pokud ma graf 3 uzly, pak reprezentace
      * muze vypadat treba takto
      * 0 -> 1 2 //z nuly vede hrana do 1 a 2
      * 1 -> 0 //z 1 vede hrana do 0
      * 2 -> //z 2 nevede hrana nikam
      */
 
     private GraphNodeIface<ENTITY>[] nodes;
 
     /**
      * Konstruktor grafu
      * @param nodeCount pocet uzlu
      */
     public LinkedGraph(int nodeCount) {
         nodes = new LinkedGraphNode[nodeCount];
         for (int i = 0; i < nodeCount; i++) {
             nodes[i] = new LinkedGraphNode<ENTITY>(i);
         }
     }
 
     /**
      * Prida hranu do grafu
      * @param from uzel, ze ktereho hrana vychazi
      * @param to uzel, do ktereho hrana vede
      */
     public void addEdge(int from, int to) {
         validateBounds(from);
         validateBounds(to);
         nodes[from].getSuccessors().add(nodes[to]);
     }
 
     /**
      * Odstrani hranu, v pripade vicenasobneho vyskytu odstrani prvni vyskyt
      * @param from uzel, ze ktereho hrana vychazi
      * @param to uzel, do ktereho hrana vede
      */
     public void removeEdge(int from, int to) {
         validateBounds(from);
         validateBounds(to);
         for (int i = 0; i < nodes[from].getSuccessors().size(); i++) {
             if (nodes[from].getSuccessors().get(i).equals(nodes[to])) {
                 nodes[from].getSuccessors().remove(i);
                 break;
             }
         }
     }
 
     @Override
     public String toString() {
         StringBuilder builder = new StringBuilder();
         for (int i = 0; i < nodes.length; i++) {
             builder.append(i + " => ");
             for (int j = 0; j < nodes[i].getSuccessors().size(); j++) {
                 if(j != 0) builder.append(" || ");
                 builder.append(nodes[i].getSuccessors().get(j).toString());
             }
             builder.append("\\n");
         }
         return builder.toString();
     }
 
     /**
      * Vrati pocet vrcholu grafu
      * @return pocet vrcholu grafu
      */
     public int getVertexCount() {
         return nodes.length;
     }
 
     /**
      * Vrati pocet hran grafu
      * @return pocet hran grafu
      */
     public int getEdgeCount() {
         int count = 0;
         for (GraphNodeIface n : nodes) {
             List<LinkedGraphNode> succ = n.getSuccessors();
             for (LinkedGraphNode s : succ) {
                 count++;
             }
         }
         return count;
     }
 
     /**
      * Provede kontrolu mezi a pripadne uzivateli vynada privetivym zpusobem
      * @param from
      * @throws IllegalArgumentException v pripade spatnych mezi
      */
     private void validateBounds(int nodeNr) throws IllegalArgumentException {
         if (nodeNr < 0)
             throw new IllegalArgumentException("Zaporne cislo uzlu");
         if (nodeNr >= nodes.length)
             throw new IllegalArgumentException("Neplatne cislo uzlu - graf ma pouze " + nodes.length + " uzlu");
     }
 
     /**
      * Vrati uzel s danym identifikatorem
      * @param id
      * @return
      */
     public GraphNodeIface getNode(int id) {
         validateBounds(id);
         return nodes[id];
     }
 
     /**
      * Uzel grafu
      * @author Pavel Micka
      * @param <ENTITY> typ objektu hodnoty
      */
     public class LinkedGraphNode<ENTITY> implements GraphNodeIface<ENTITY> {
 
         private int id;
         private List<GraphNodeIface> successors;
         private ENTITY value;
 
         public LinkedGraphNode(int id, ENTITY value) {
             this.id = id;
             this.value = value;
             this.successors = new LinkedList<GraphNodeIface>();
         }
 
         public LinkedGraphNode(int id) {
             this.id = id;
             this.value = null;
             this.successors = new LinkedList<GraphNodeIface>();
         }
 
         /**
          * @return the id
          */
         public int getId() {
             return id;
         }
 
         /**
          * @return the successors
          */
         public List<GraphNodeIface> getSuccessors() {
             return successors;
         }
 
         /**
          * @return the value
          */
         public ENTITY getValue() {
             return value;
         }
 
         /**
          * @param value the value to set
          */
         public void setValue(ENTITY value) {
             this.value = value;
         }
 
         @Override
         public String toString() {
             return "GraphNode >> id: " + getId() + ", Value: " + (value != null ? value.toString() : "null");
         }
     }
 }

 /**
  * Operace, ktere by mel splnovat graf
  * @author Pavel Micka
  */
 public interface GraphIface<ENTITY> {
 
     /**
      * Prida hranu do grafu
      * @param from uzel, ze ktereho hrana vychazi
      * @param to uzel, do ktereho hrana vede
      */
     public void addEdge(int from, int to);
 
     /**
      * Vrati pocet hran grafu
      * @return pocet hran grafu
      */
     public int getEdgeCount();
 
     /**
      * Vrati uzel s danym identifikatorem
      * @param id
      * @return
      */
     public GraphNodeIface getNode(int id);
 
     /**
      * Vrati pocet vrcholu grafu
      * @return pocet vrcholu grafu
      */
     public int getVertexCount();
 
     /**
      * Odstrani hranu, v pripade vicenasobneho vyskytu odstrani prvni vyskyt
      * @param from uzel, ze ktereho hrana vychazi
      * @param to uzel, do ktereho hrana vede
      */
     public void removeEdge(int from, int to);
     
     /**
      * Operace, ktere by mel splnovat uzel grafu
      * @param <ENTITY>
      */
     public interface GraphNodeIface<ENTITY> {
 
         /**
          * @return the id
          */
         public int getId();
 
         /**
          * @return the successors
          */
         public List<GraphNodeIface> getSuccessors();
 
         /**
          * @return the value
          */
         public ENTITY getValue();
 
         /**
          * @param value the value to set
          */
         public void setValue(ENTITY value);
     }
 }

Literatura

KOLÁŘ, Josef. Teoretická informatika. 2. vyd. Praha : Česká informatická společnost, 2004. 205 s. ISBN 80-900853-8-5.

Neorientovaný graf

Orientovaný graf

Tah, sled, cesta, souvislost

Planarita grafu

Nezávislost grafu

Barevnost grafu

Vrcholové pokrytí grafu

Klika grafu

Reprezentace grafu

Matice sousednosti

Matice incidence

Spojová reprezentace

Kód

Literatura

Doporučujeme