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, w₀), (w₀, w₁), ... , (w_n, 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 G₁ = (V₁, E₁) nim. graafi G = (V, E) alamgraafiks, kui V₁ on hulga V alamhulk ja E₁ on E ühisosa hulgaga V₁xV₁ (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 G₁=(V, E₁) ja G₂=(V,E₂) korrutis on graaf G=(V, E), kus

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

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

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

Graafi töötlemine

#!/usr/bin/env python3

import random


class Graph(object):

    __name = "Graph object"
    __first_vertex = None
    __info = 0

    def __init__(self, name):
        self.__name = name

    def get_name(self):
        return self.__name

    def set_name(self, name):
        self.__name = name

    def get_first_vertex(self):
        return self.__first_vertex

    def set_first_vertex(self, vertex):
        self.__first_vertex = vertex

    def get_info(self):
        return self.__info

    def set_info(self, info):
        self.__info = info

    def __str__(self):
        nl = "\n"
        res = nl + self.get_name()
        v = self.get_first_vertex()
        while v:
            res += nl + str(v) + " -->"
            a = v.get_first_out_arc()
            while a:
                res += " " + str(a)
                res += " (" + v.get_name() + "->" + a.get_target(). \
                    get_name() + ")"
                a = a.get_next()
            v = v.get_next()
        return res

    def matrix(self):
        v = self.get_first_vertex()
        n = 0
        while v:
            v.set_info(n)
            n += 1
            v = v.get_next()
        res = [[0] * n for row in range(n)]
        v = self.get_first_vertex()
        while v:
            a = v.get_first_out_arc()
            while a:
                i = v.get_info()
                j = a.get_target().get_info()
                res[i][j] += 1
                a = a.get_next()
            v = v.get_next()
        return res

    def create_vertex(self, name):
        res = Vertex(name)
        res.set_next(self.get_first_vertex())
        self.set_first_vertex(res)
        return res

    def create_arc(self, name, fr, to):
        res = Arc(name)
        res.set_next(fr.get_first_out_arc())
        fr.set_first_out_arc(res)
        res.set_target(to)
        return res

    def create_random_tree(self, number_of_vertices):
        if number_of_vertices < 1:
            return
        vlist = []
        for from_i in range(number_of_vertices):
            name = "v" + str(number_of_vertices - from_i)
            vlist.append(self.create_vertex(name))
            if from_i > 0:
                to_i = random.randint(0, from_i - 1)
                from_v = vlist[from_i]
                to_v = vlist[to_i]
                self.create_arc("a" + to_v.get_name() +
                                "_" + from_v.get_name(), to_v, from_v)
                self.create_arc("a" + from_v.get_name() +
                                "_" + to_v.get_name(), from_v, to_v)

    def create_random_simplegraph(self, number_of_vertices, number_of_edges):
        self.set_first_vertex(None)
        if number_of_vertices < 1:
            return
        if (number_of_edges < number_of_vertices - 1) or \
                (number_of_edges > number_of_vertices * (number_of_vertices - 1) / 2):
            raise ValueError("Wrong number of edges: " + str(number_of_edges))
        self.create_random_tree(number_of_vertices)
        connected = self.matrix()
        vlist = []
        v = self.get_first_vertex()
        while v:
            vlist.append(v)
            v = v.get_next()
        remaining_edges = number_of_edges - number_of_vertices + 1
        while remaining_edges > 0:
            i_v1 = random.randint(0, number_of_vertices - 1)
            i_v2 = random.randint(0, number_of_vertices - 1)
            if i_v1 == i_v2:
                continue
            if (connected[i_v1][i_v2] > 0) or (connected[i_v2][i_v1] > 0):
                continue
            v1 = vlist[i_v1]
            v2 = vlist[i_v2]
            self.create_arc("a" + v1.get_name() +
                            "_" + v2.get_name(), v1, v2)
            self.create_arc("a" + v2.get_name() +
                            "_" + v1.get_name(), v2, v1)
            connected[i_v1][i_v2] = 1
            connected[i_v2][i_v1] = 1
            remaining_edges -= 1


class Vertex(object):

    __name = "Vertex object"
    __first_out_arc = None
    __next = None
    __info = 0

    def __init__(self, name):
        self.__name = name

    def get_name(self):
        return self.__name

    def set_name(self, name):
        self.__name = name

    def get_first_out_arc(self):
        return self.__first_out_arc

    def set_first_out_arc(self, arc):
        self.__first_out_arc = arc

    def get_next(self):
        return self.__next

    def set_next(self, next_vertex):
        self.__next = next_vertex

    def get_info(self):
        return self.__info

    def set_info(self, info):
        self.__info = info

    def __str__(self):
        return self.get_name() + " " + str(self.get_info())


class Arc(object):

    __name = "Arc object"
    __next = None
    __target = None
    __info = 0

    def __init__(self, name):
        self.__name = name

    def get_name(self):
        return self.__name

    def set_name(self, name):
        self.__name = name

    def get_next(self):
        return self.__next

    def set_next(self, next_arc):
        self.__next = next_arc

    def get_target(self):
        return self.__target

    def set_target(self, target):
        self.__target = target

    def get_info(self):
        return self.__info

    def set_info(self, info):
        self.__info = info

    def __str__(self):
        return self.get_name() + " " + str(self.get_info())


def main():
    """
    Main method.
    """
    g1 = Graph("G")
    g1.create_random_simplegraph(6, 10)
    print(g1)
    m = g1.matrix()
    print(m)


if __name__ == '__main__':
    main()

Kauguste arvutamine

Ülesanne: arvutada etteantud kaarepikkuste maatriksi järgi lühimad teepikkused kõigi tipupaaride vahel.

Kaarepikkuste maatriks: element [i][j] on kaare i->j pikkus (positiivne reaalarv). Lihtsustatud juhul on iga kaare pikkuseks 1 ühik. Peadiagonaalil on nullid, puuduva kaare korral on pikkuseks "lõpmatus".

Floyd-Warshalli algoritm

def dist_matrix(self):
    v = self.get_first_vertex()
    n = 0
    while v:
        v.set_info(n)
        n += 1
        v = v.get_next()
    res = [[0] * n for row in range(n)]
    v = self.get_first_vertex()
    max_len = 0
    while v:
        a = v.get_first_out_arc()
        while a:
            i = v.get_info()
            j = a.get_target().get_info()
            res[i][j] = a.get_info()
            max_len = max(max_len, res[i][j])
            a = a.get_next()
        v = v.get_next()
    n = len(res)
    infinity = max_len * n + 1
    for i in range(0, n):
        for j in range(0, n):
            if res[i][j] <= 0:
                res[i][j] = infinity
        res[i][i] = 0
    return res

@staticmethod
def floyd_warshall(m):
    n = len(m)
    if n > 0:
        for k in range(0, n):
            for i in range(0, n):
                for j in range(0, n):
                    new = m[i][k] + m[k][j]
                    if new < m[i][j]:
                        m[i][j] = new

        

Graafi loomine maatriksist

def from_matrix(self, mat):
    n = len(mat)
    if n > 0:
        vlist = []
        for k in range(n-1, -1, -1):  # create_vertex reverses list
            vk = self.create_vertex("v" + str(k+1))
            vlist.insert(0, vk)
        for i in range(0, n):
            for j in range(n-1, -1, -1):  # create_arc reverses list
                for d in range(0, mat[i][j]):  # duplicate arcs possible
                    fromv = vlist[i]
                    tov = vlist[j]
                    aname = "a" + fromv.get_name() + "_" + tov.get_name()
                    if d > 0:  # duplicate arc
                        aname = aname + "_" + str(mat[i][j] - d)
                    self.create_arc(aname, fromv, tov)

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).

Topoloogiline sorteerimine

def topol_sort(self):
    cycle_found = False
    order = []
    n = 0
    v = self.get_first_vertex()
    while v:
        v.set_info(0)
        n = n + 1
        v = v.get_next()
    v = self.get_first_vertex()
    while v:
        a = v.get_first_out_arc()
        while a:
            to = a.get_target()
            to.set_info(to.get_info()+1)
            a = a.get_next()
        v = v.get_next()
    start = []
    v = self.get_first_vertex()
    while v:
        if v.get_info() == 0:
            start.append(v)
        v = v.get_next()
    if len(start) == 0:
        cycle_found = True
    while not cycle_found and len(start) > 0:
        cur = start.pop()
        order.append(cur)
        aout = cur.get_first_out_arc()
        while aout:
            ato = aout.get_target()
            ato.set_info(ato.get_info()-1)
            if ato.get_info() <= 0:
                start.append(ato)
            aout = aout.get_next()
    if len(order) != n:
        cycle_found = True
    if cycle_found:
        v = self.get_first_vertex()
        while v:
            v.set_info(0)
            v = v.get_next()
    else:
        i = 0
        for v1 in order:
            i = i + 1
            v1.set_info(i)

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)

def traverse(self, source):
    v = self.get_first_vertex()
    source_exists = False
    while v:
        v.set_info(0)  # white
        if v == source:
            source_exists = True
        v = v.get_next()
    vq = []
    if source_exists:
        vq.append(source)
        source.set_info(1)  # gray
    else:
        raise ValueError("Wrong source vertex")
    while vq:
        vert = vq.pop()  # LIFO (DFS) pop()  vs. FIFO (BFS) pop(0)
        print(vert.get_name(), end=' ')  # process vert
        vert.set_info(2)  # black
        a = vert.get_first_out_arc()
        while a:
            w = a.get_target()
            if w.get_info() == 0:  # white?
                vq.append(w)
                w.set_info(1)  # gray
            a = a.get_next()

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

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

def shortest_paths_from(self, source):
    n = 0
    maxlen = 0
    source_found = False
    v = self.get_first_vertex()
    while v:
        if v == source:
            source_found = True
        n = n + 1
        a = v.get_first_out_arc()
        while a:
            maxlen = max(maxlen, a.get_info())
            a = a.get_next()
        v = v.get_next()
    infinity = n * maxlen + 1
    if source_found:
        v = self.get_first_vertex()
        while v:
            v.__previous = None
            v.set_info(infinity)
            v = v.get_next()
        source.set_info(0)
        vq = [source]
        while vq:
            minv = None
            minlen = infinity
            for vert in vq:
                if vert.get_info() < minlen:
                    minv = vert
                    minlen = minv.get_info()
            vq.remove(minv)
            a = minv.get_first_out_arc()
            while a:
                to = a.get_target()
                newlen = minlen + a.get_info()
                if to.get_info() >= infinity:
                    vq.append(to)
                if newlen < to.get_info():
                    to.set_info(newlen)
                    to.__previous = minv
                a = a.get_next()
    else:
        raise ValueError("source vertex not found")

Näide.

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.

 

Lühimate teede leidmine graafis

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

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