729G46 Informationsteknologi och programmering¶

Tema 2, Föreläsning 2.3¶

Johan Falkenjack, johan.falkenjack@liu.se¶

Föreläsningsöversikt¶

  • Grafer och grafterminologi
  • Tupler
  • Träd

Grafer¶

Grafer¶

  • Grafer används för att representera struktur hos en mängd (information/data), hur element är relaterade till varandra.
  • Exempel på element vi skulle kunna tänka oss ha en strukturell komponent:
  • $S = \{ \text{Linköping}, \text{Göteborg}, \text{Jönköping}, \text{Malmö}, \text{Katrineholm}, \text{Stockholm}, \text{Umeå} \}$
  • $M = \{ \text{Ada}, \text{Bert}, \text{Cilla}, \text{Dan}, \text{Evy} \}$

Exempel¶

No description has been provided for this image

  • Tågförbindelser mellan olika städer (Notera att positionerna inte exakt motsvarar var städerna ligger geografiskt)

Exempel¶

No description has been provided for this image

  • Tågförbindelser mellan olika städer (Notera att positionerna inte exakt motsvarar var städerna ligger geografiskt)

Exempel¶

No description has been provided for this image

  • Tågförbindelser mellan olika städer (Notera att positionerna inte exakt motsvarar var städerna ligger geografiskt)

Exempel¶

No description has been provided for this image

  • Socialt nätverk där användare kan bli vänner med varandra

Exempel¶

No description has been provided for this image

  • Socialt nätverk där användare kan bli vänner med varandra

Grafer¶

No description has been provided for this image No description has been provided for this image

  • Grafer har
    • noder / hörn (eng. vertex (pl. vertices) / node) och
    • bågar / kanter (eng. arc / edge)
  • Grafer kan vara riktade eller oriktade

Tupler¶

  • Mängd: samling av godtyckliga objekt som kallas element, utan inombördes ordning. Skrivs inom klammerparenteser.
    • T.ex. $\{ a, b, c, d \}$, där $\{ a, b, c, d \} = \{ b, a, d, c \}$
  • Tupel: ordnat par med inombördes ordning. Skrivs inom bågparenteser
    • T.ex. $(a, b)$, där $(a, b) \neq (b, a)$
  • n-Tupel: Tupel av längden $n$
    • T.ex. en 3-tupel $(f, b, c)$, även kallad för en trippel

Matematisk representation av en oriktad graf¶

No description has been provided for this image

  • En graf består av en mängd noder, $V$, och en mängd bågar $E$.
    • För exempelgrafen är $V = \{ a, b, c, d, e \}$
  • En oriktad båge har ingen specifik start- eller slutnod, så vi representerar en oriktad båge som en mängd, t.ex. $\{a, b\}$
    • För exempelgrafen är $E = \{\{a, b\}, \{a, c\}, \{b, d\}, \{c, d\}, \{c, e\}, \{d, e\}\}$
  • Vi kan då definiera grafen $G$ som: $G = (V, E)$
  • Grafen är en tupel, eftersom ordningen mellan $V$ och $E$ spelar roll. Den första mängden är noderna, den andra mängden är bågarna.

Matematisk representation av en riktad graf¶

No description has been provided for this image

  • En graf består av en mängd noder, $V$, och en mängd bågar $E$.
    • För exempelgrafen är $V = \{ a, b, c, d, e \}$
  • En riktad båge har en start- och en slutnod, så vi representerar en riktad båge som en tupel, t.ex. $(b, a)$
    • För exempelgrafen är $E = \{(b, a), (b, d), (c, a), (d, c), (d, e), (e,c)\}$
  • Vi kan då definiera grafen $G$ som: $G = (V, E)$
  • Grafen är en tupel, eftersom ordningen mellan $V$ och $E$ spelar roll. Den första mängden är noderna, den andra mängden är bågarna.

Delgrafer¶

No description has been provided for this image A

No description has been provided for this image B

  • En delgraf, $G' = (V', E')$ är en delgraf till $G$ om $V' \subseteq V$ och $E' \subseteq E$.
    • $V_A = \{ a, b, c, d, e \}$
    • $E_A = \{(b, a), (b, d), (c, a), (d, c), (d, e), (e,c)\}$
    • $V_B = \{ c, d, e \}$
    • $E_B = \{ (d, c), (d, e), (e,c)\}$
    • $V_B \subseteq V_A$ och $E_B \subseteq E_A$, alltså är $B$ en delgraf till $A$

Delgrafer¶

No description has been provided for this image A

No description has been provided for this image B

  • En delgraf, $G' = (V', E')$ är en delgraf till $G$ om $V' \subseteq V$ och $E' \subseteq E$.
    • $V_A = \{ a, b, c, d, e \}$
    • $E_A = \{(b, a), (b, d), (c, a), (d, c), (d, e), (e,c)\}$
    • $V_C = \{ c, d, e \}$
    • $E_C = \{ (d, c), (d, e), (c, e)\}$
    • $V_C \subseteq V_A$ men $E_C \nsubseteq E_A$, alltså är $C$ inte en delgraf till $A$

Noder och valens¶

No description has been provided for this image

  • Noder som har en båge mellan sig kallas grannar (eng. neighbors).
  • En nods grad eller valens (eng. degree eller valency) är antalet bågar som ansluter till noden.
    • Om bågarna en nod ingår i är riktade kan man prata om en nods in- och utvalens eller in- och utgrad .
  • Exempel:
    • Noden $d$ har valensen 3, mer specifikt,
    • Invalens 1
    • Utvalens 2

Vandring, väg, stig, krets, cykel¶

  • vandring (walk): en följd av noder i en graf, $(v_1, v_2, ... v_k)$ där det mellan varje $v_i$ och $v_{i+1}$ finns en båge.
  • väg (trail): en vandring som inte använder samma båge mer än en gång
  • stig (path), är en väg som inte besöker samma nod två gånger
  • En sammanhängande graf är en graf där det finns en vandring mellan varje par av noder.
  • En krets (circuit) eller en sluten väg är en väg $(v_1, v_2, ... v_k)$ där $v_1 = v_k$, dvs som börjar och slutar i samma nod
  • En cykel (cycle) eller en sluten stig är en stig $(v_1, v_2, ... v_k)$ där $v_1 = v_k$, dvs som börjar och slutar i samma nod

Vandring, väg, stig, krets, cykel¶

No description has been provided for this image

  • $(a, b, c, d, b, a)$ är en vandring, men
    • inte en väg eftersom den använder bågen $\{a, b\}$ mer än en gång
    • inte en stig eftersom den besöker t.ex. noden $b$ flera gånger
    • varken en krets eller cykel

Vandring, väg, stig, krets, cykel¶

No description has been provided for this image

  • $(a, b, c, a, d)$ är en vandring och en väg, men
    • inte en stig eftersom noden $a$ finns med mer än en gång.

Vandring, väg, stig, krets, cykel¶

No description has been provided for this image

  • $(a, b, c)$ är en vandring, en väg och en stig.

Vandring, väg, stig, krets, cykel¶

No description has been provided for this image

  • $(a, b, c, d, e, c, a)$ är en krets men
    • inte en cykel eftersom noden $c$ besöks mer än en gång

Vandring, väg, stig, krets, cykel¶

No description has been provided for this image

  • $(a, b, c, d, a)$ är en krets och en cykel

Isomorfi¶

  • Två ritade grafer är isomorfa om strukturen är den samma men graferna är ritade på olika sätt

Drawing Drawing Drawing Drawing

Viktade grafer¶

No description has been provided for this image

  • I en viktad graf har man tilldelat varje båge en vikt
  • Exempel: Restid mellan olika städer

Träd - ett specialfall av grafer¶

Träd¶

No description has been provided for this image

  • En graf är ett träd om grafen är
    • sammanhängande
    • utan cykler (acyklisk)
  • Man kan också beskriva ett träd som en graf där det mellan varje par av noder finns en unik, enkel väg
  • Noder med grad 1 kallas för löv
  • Träd har alltid $|V|-1$ bågar

Träd - egenskaper¶

No description has been provided for this image

  • Om man lägger till en båge till ett träd får man en cyklisk graf
    • Ett träd är sammanhängande, dvs det finns en båge mellan varje par av noder. Om vi har ett träd med noderna $v$ och $w$ och lägger till den nya bågen $\{v, w\}$ kommer det nu finnas två vägar mellan $v$ och $w$. Vi kan vandra från $v$ till $w$ med den ursprungliga vägen, för att sedan gå från $w$ till $v$ med den nya bågen. Vi har en cykel.

Träd - egenskaper¶

No description has been provided for this image

  • Om man tar bort en båge från ett träd får man en osammanhängande graf
    • Ett träd har är sammanhängande och har inga cykler, dvs det finns exakt en väg mellan varje par av noder. Om vi har bågen $\{v, w\}$ vet vi att det är den enda vägen mellan $v$ och $w$. Om vi tar bort $\{v, w\}$ försvinner alltså den enda vägen mellan $v$ och $w$ och grafen blir osammanhängande.

Spännande (eller uppspännande) träd¶

  • Om $G=(V, E)$ är en sammanhängande graf, så kan vi ta fram ett spännande träd, $G'$ för $G$.
  • $G'$ är ett spännande träd för $G$ om
    • $G' = (V, E')$ där $E' ⊆ E$
    • $G'$ är ett träd
  • Ett spännande träd för grafen $G$ innehåller alltså alla noderna från $G$, men inte nödvändigtvis alla bågar.
  • Med en grafs spännande träd har vi exakt en väg mellan varje par av noder eftersom ett träd är sammanhängande och inte innehåller några cykler

Exempel, spännande träd¶

Drawing Drawing

Exempel, spännande träd¶

Drawing Drawing

Minimalt uppspännande träd för en (viktad) graf¶

  • Det uppspännande träd som har den minsta viktsumman (summan av alla bågars vikter i en graf)
  • Kruskals algoritm för att ta fram ett minimalt uppspännande träd
    1. Sortera bågarna efter ökande vikt
    2. Välj en ny båge med lägst vikt
    3. Kontrollera att bågen inte introducerar en cykel
    4. Om den inte introducerar en cykel, lägg till den till det minimalt uppspännande trädet
    5. Upprepa från Steg 2 tills vi har $|V|-1$ stycken bågar i trädet

Tillämpning av Kruskals algoritm¶

No description has been provided for this image

  • Mål: 5-1=4 bågar

Tillämpning av Kruskals algoritm¶

No description has been provided for this image

  • Mål: 5-1=4 bågar
  • Bågen $\{ c, d \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Uppnått: 1 båge

Tillämpning av Kruskals algoritm¶

No description has been provided for this image

  • Mål: 5-1=4 bågar
  • Bågen $\{ c, d \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Bågen $\{ b, c \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Uppnått: 2 bågar

Tillämpning av Kruskals algoritm¶

No description has been provided for this image

  • Mål: 5-1=4 bågar
  • Bågen $\{ c, d \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Bågen $\{ b, c \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Bågen $\{ b, d \}$ med vikten 1 är en av bågarna med lägst vikt men skulle introducera en cykel och skall därför inte ingå.
  • Uppnått: 2 bågar

Tillämpning av Kruskals algoritm¶

No description has been provided for this image

  • Mål: 5-1=4 bågar
  • Bågen $\{ c, d \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Bågen $\{ b, c \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Bågen $\{ b, d \}$ med vikten 1 är en av bågarna med lägst vikt men skulle introducera en cykel och skall därför inte ingå.
  • Bågen $\{ d, e \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Uppnått: 3 bågar

Tillämpning av Kruskals algoritm¶

No description has been provided for this image

  • Mål: 5-1=4 bågar
  • Bågen $\{ c, d \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Bågen $\{ b, c \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Bågen $\{ b, d \}$ med vikten 1 är en av bågarna med lägst vikt men skulle introducera en cykel och skall därför inte ingå.
  • Bågen $\{ d, e \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Bågen $\{ a, b \}$ med vikten 1 är en av bågarna med lägst vikt och skall ingå.
  • Uppnått: 4 bågar

Tillämpning av Kruskals algoritm¶

No description has been provided for this image

  • Mål: 5-1=4 bågar
  • Resultatet har 4 bågar med en total vikt av 4, grafen är sammanhängande, inga cykler existerar -> Vi har ett minsta uppspännande träd.

Rotade träd¶

  • Ett träd där en nod definierats som som rotnod
  • Ett rotat träd får en hierarkisk struktur

Drawing Drawing Drawing

Riktade rotade träd¶

No description has been provided for this image

  • Vi kan självklart även introducera riktning i ett rotat träd

Rotade träd med ordning¶

  • Vi kan även introducera ordning i ett träd
  • Dvs att ordningen mellan barnen i ett träd är viktig (ex. ett släktträd med enbart döttrar skulle kunna ordnas efter födsloordning i varje generation)

Drawing Drawing

XML - hierarkisk informationsstruktur¶

  • XML är en hierarkisk informationsstruktur
    • Alla element förutom rot-elementet har exakt en förälder
    • Rot-elementet har exakt 0 förädrar

XML-exempel¶

<book>
    <author>
        <firstname>Ludwig</firstname>
        <lastname>Wittgenstein</lastname>
    </author>
    <title>Tractatus logico-philosophicus</title>
    <year>1921</year>
    <contents>
        <chapter>
            <title>Inledning</title>
            <section>
                <title>1. Wittgenstein och Tractatus</title>
                <paragraph>
                ...
                </paragraph>
            </section>
        </chapter>
    </contents>
</book>

XML-exempel¶

Binärt träd¶

  • Speciell typ av träd där varje nod får ha som mest två barn
  • Kan vara riktade eller oriktade
  • Om det är ordnat: vänster barn, höger barn
  • Exempel på tillämpning: Huffmanträd för komprimering (mer på Begreppssem 2)

Drawing Drawing Drawing

Tillämpning: Lingvistik - Frasstrukturträd¶

No description has been provided for this image

  • Eng. Phrase Structure Grammar tree
  • Ett sätt att representera meningar i naturliga språk baserat på grammatiska regler.
  • Exempelvis för meningen "Mannen bet hunden."
  • Mer om detta i under Termin 2 i 729G49 Språk och datorer och Termin 4 i 729G86 Språkteknologi.

Tillämpning: Programmering - Abstrakta syntaxträd¶

No description has been provided for this image

  • Motsvarar frasstrukturträd men för formella språk som programmeringsspråk.
  • Används ofta som en intern representation av ett program och kan ibland manipuleras av programtolken, eller speciellt av en kompilator, för att optimera ett program.
  • Exempel: Euklides algoritm för största gemensamma nämnare:
def greatest_common_denom_euclid(a, b):
    while b != 0:
        if a > b:
            a = a - b
        else:
            b = b - a
    return a

Tillämpning: Artificiell Intelligens/Robotik - Beteendeträd¶

(By Aliekor at English Wikipedia, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=124384566)

  • Vilka handlingar kan utföras just nu givet robotens tillstånd, och vilket tillstånd leder varje handling till.
  • Mer om detta Termin 3 i 729G78 Artificiell intelligens.

Tillämpning: Artificiell Intelligens / Statistisk Modellering - Bayesianska Nätverk¶

  • Modellera komplexa statistiska förhållanden.
  • Mer om detta Termin 3 i 729G78 Artificiell intelligens.

Tillämpning: Human Factors - Social Network Analysis¶

  • Studerar hur personer och/eller organisationer kommunicerar och förhåller sig till varandra.
  • Mer om detta Termin 5 i 729G84 Människan i komplexa system och Termin 1 på masterprogrammet i 769A19 Human Factors.

Tillämpning: Information Retrieval - Page Rank¶

  • Algoritmen som Google och flera andra sökmotorer bygger på (efter de första 10 träffarna som numera tenderar att vara riktad reklam...)
  • Mer om detta Termin 3 i 729G78 Artificiell intelligens (ja, sökmotorer ÄR en del av forskningsområdet artificiell intelligens).