Grafer og Netværk

import matplotlib
if not hasattr(matplotlib.RcParams, "_get"):
    matplotlib.RcParams._get = dict.get

Grafer og Netværk#

Vi er omgivet af netværk alle vegne: veje, jernbaner, internettet, elektronik, og venskaber (både forbindelser i virkeligheden og på sociale netværk).

I matematik kan vi repræsentere netværk som grafer. En graf består af knuder der er forbundet med kanter. Vi tegner dem ved hjælp af cirkler (knuder) og linjer (kanter). En kant går imellem to knuder. To knuder er naboer hvis der er en kant imellem dem.

Eksempel: Her er en graf med 5 knuder.

Eksempel1

Positionen af knuderne og længden af kanter på tegningen betyder ikke noget. Vi er kun interesserede i hvordan knuderne er forbundet med hinanden. Nedenstående tegninger repræsenterer alle den samme graf.

Eksempel2

Hvilken af nedenstående grafer er forskellig fra de andre?

Graden på en knude er antallet af naboer. I nedenstående graf har knuden \(B\) grad \(4\). Når vi skal beskrive en graf uden at tegne den så skrives kanterne som par af knuder, f.eks. \((A, B)\).

Eksempel1

  • Hvor mange knuder har følgende graf?

  • Hvor mange kanter?

  • Hvad er graden af knude \(A\)?

Opsætning#

import networkx as nx
import matplotlib.pyplot as plt

Grafer i Python#

Vi kan tegne grafer i Python ved hjælp af pakken networkx. Kør nedenstående kode og svar på

  • hvor mange knuder er der i grafen \(G\)?

  • hvor mange kanter?

  • hvad er den maksimale grad i grafen? (hvor mange naboer har den knude med flest naboer?)

### Kode der indsætter knuderne her:

G = nx.Graph()
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_node(5)
G.add_node(6)
G.add_node(7)
G.add_node(8)

### ******************************
### Kode der indsætter kanterne her:

G.add_edge(1,2)
G.add_edge(3,2)
G.add_edge(4,2)
G.add_edge(1,5)
G.add_edge(3,7)
G.add_edge(6,1)
G.add_edge(6,3)
G.add_edge(7,8)
G.add_edge(8,5)
G.add_edge(8,2)
G.add_edge(8,3)
G.add_edge(6,5)

### ******************************
### Tegner grafen

nx.draw(G, pos=nx.planar_layout(G), with_labels=True)
plt.show(block=True)

I nedenstående kodecelle bygger vi en ny graf \(F\). Grafen har 5 knuder nummereret fra 1 til 5. Der er ingen kanter i grafen.

F = nx.Graph()
F.add_node(1)
F.add_node(2)
F.add_node(3)
F.add_node(4)
F.add_node(5)
### **********
### Indsæt kode der indsætter kanterne her:




### **********
### Tegner grafen

nx.draw(F, pos=nx.planar_layout(F), with_labels=True)
plt.show(block=True)

Funktionen add_edge(i, j) laver en kant mellem knude \(i\) og \(j\).

Indsæt kanter ved hjælp af add_edge funktionen, så grafen har samme kanter som grafen på tegningen nedenunder.

Nabokommando#

Vi kan bruge følgende kommandoer/funktioner i networkx til at undersøge grafen med.

  • list(G.nodes): returnerer en liste med alle knuderne i \(G\).

  • list(G.neighbors(i)): returnerer en liste med alle knude \(i\)’s naboer.

  • G.degree[i]: returnerer graden af knude \(i\).

Vi vender tilbage til grafen \(G\) som defineret tidligere.

Kør følgende kode. Lav den om så den udskriver nabolisten til knude \(4\) og graden af knude \(4\).

### ******************************
### Undersøg grafen G:

print('Grafen har', len(list(G.nodes())), 'knuder')
print('Knudeliste:', list(G.nodes()))
print('Naboer til knude 3:', list(G.neighbors(3)))
print('Knude 8 har grad:', G.degree(8))

### ******************************
### Tegner grafen

nx.draw(G, pos=nx.planar_layout(G), with_labels=True)
plt.show(block=True)

Tilføj kode nedenfor der gennemløber alle knuder i grafen \(G\) ved hjælp af en løkke og beregner og printer summen af graderne.

# Find summen af graderne:

Tilføj kode nedenfor der gennemløber alle knuder i grafen \(G\) og finder den maksimale grad i grafen.

# Find den maksimale grad:

Farver#

Vi kan ændre på farverne på knuder og kanter enkeltvis ved at skrive følgende:

G.edges[i, j]['color'] = 'red',

G.nodes[i]['color'] = 'green'.

Tilføj kode til nedenstående graf der

  • farver alle naboer til knude \(3\) grøn.

  • farver alle kanterne der har et endepunkt i knude \(3\) røde.

### Farv grafen:
# Tilføj farver til kanter og knuder her



### Tegner grafen

e_colors = [c for u,v,c in G.edges.data('color', default='black')]
n_colors = [c for u, c in G.nodes.data('color', default='blue')]

nx.draw(G, pos=nx.planar_layout(G), edge_color = e_colors, node_color = n_colors, with_labels=True)
plt.show(block=True)

Korteste stier#

En vandring af længde \(k\) i en graf er en følge af \(k\) kanter

\[ (v_0,v_1),(v_1,v_2),(v_2,v_3),\dots,(v_{k-1},v_k). \]

En vandring angives dog for det meste bare som følgen af de knuder den går igennem \(v_0,v_1,v_2,\dots,v_k\). En sti er en vandring hvor alle knuder er forskellige.

Eksempel: Figur \((a)\) viser vandringen \(B\), \(C\), \(E\), \(B\), \(A\), \(D\). Figur \((b)\) viser stien \(D\), \(A\), \(B\), \(E\).

Kør nedenstående kode og se grafen.

Tilføj kode der farver kanterne på en sti fra knude \(0\) til \(4\) (der er mange forskellige stier fra \(0\) til \(4\), du skal bare farve en af dem).

G = nx.Graph()
G.add_node(0)
G.add_node(1)
G.add_node(2)
G.add_node(3)
G.add_node(4)
G.add_node(5)
G.add_node(6)
G.add_node(7)
G.add_node(8)
G.add_node(9)

### **********
### Kanter

G.add_edge(0,1)
G.add_edge(1,3)
G.add_edge(3,6)
G.add_edge(4,6)
G.add_edge(0,8)
G.add_edge(7,1)
G.add_edge(2,4)
G.add_edge(7,6)
G.add_edge(2,3)
G.add_edge(5,3)
G.add_edge(8,5)
G.add_edge(6,8)
G.add_edge(0,5)
G.add_edge(7,8)
G.add_edge(2,9)
G.add_edge(4,9)

### **********
### Indsæt kode farver kanter på en sti fra 0 til 4 her:


### **********
### Tegner grafen

colors = [c for u,v,c in G.edges.data('color', default='black')]
n_colors = [c for u, c in G.nodes.data('color', default='blue')]

nx.draw(G, pos=nx.planar_layout(G), edge_color = colors, node_color = n_colors, with_labels=True)
plt.show(block=True)

Hvor lang er den korteste sti fra knude \(0\) til knude \(4\)? Hvor lang er den længste sti fra knude \(0\) til knude \(4\) (husk at en sti kun må gå igennem en knude en gang)?

Korteste sti#

I den følgende del gennemgår vi en algoritme til at finde en korteste sti i en graf fra en knude \(v\) til alle andre knuder i en graf. Vi vil udvikle den lidt ad gangen indtil vi har den endelige algoritme.

Vi siger at en knude \(u\) har afstand \(d\) til knude \(v\), hvis længden af den korteste sti mellem \(u\) og \(v\) er \(d\). Algoritmen skal lave en afstandsliste hvor der står \(d\) på plads \(i\) hvis afstanden mellem knude \(0\) og knude \(i\) er \(d\).

Eksempel. Afstandslisten for nedenstående graf er \([0, 2, 3, 1, 1, 2]\).

Den overordnede ide for algoritmen er først at finde alle knuder der har afstand \(1\) fra knude \(0\), så alle af afstand \(2\), osv.

Afstand 1#

Vi skal nu lave den første del af algoritmen, der finder alle knuder med afstand \(1\) til vores startknude knude \(0\). Kig på nedenstående kode. I afstandslisten Afstandsliste er der en indgang for hver knude. Til at starte med står der \(-1\) på alle pladser.

#############################################
### Laver og opdaterer afstandsliste

Afstandsliste = [-1]*10    # Laver "tom" Afstandsliste af længde 10.

#### Indsæt kode her 



#### Printer afstandslisten
print("Afstandsliste:\n", Afstandsliste)

##################
### Tegner grafen

nx.draw(G, pos=nx.planar_layout(G), with_labels=True)
plt.show(block=True)

Skriv kode ovenfor der automatisk modificerer afstandslisten, så der står den rigtige afstand for alle knuder der har afstand højst \(1\) til knude \(0\). For alle andre knuder skal der stadig stå \(-1\).

Vink: Brug en for-løkke og G.neighbors(i).

Afstand 2#

Vi skal nu finde alle knuder med afstand \(2\) fra knude \(0\). Alle knuder der har afstand \(2\) fra knude \(0\) må være nabo til en knude der har afstand \(1\) fra knude \(0\).

Hvorfor?

Vi skal nu modifierer afstandslisten fra før, så der står den rigtige afstand for alle knuder der har afstand højst \(2\) til knude \(0\). For alle andre knuder skal der stadig stå \(-1\).

Tilføj kode nedenfor, der automatisk modifierer afstandslisten fra før.

Husk: Der skal ikke stå \(2\), hvor der før stod \(0\) eller \(1\) i afstandslisten.

####################################
##### Skriv kode modificerer afstandslisten

for i in range(10):
    if Afstandsliste[i] == 1:
        ####Tilføj kode her ######

        ####

Alle afstande#

Vi kan finde afstanden fra knude \(0\) til alle knuder i grafen ved at fortsætte på samme måde. Dvs. runde for runde finde alle de knuder der har afstand en mere end i forrige runde.

Forklar hvorfor, at den længste afstand fra en knude til en anden kan højst være antallet af knuder i grafen minus en.

Nedenstående kode indeholder en funktion BFS(v,G) finder afstande til alle knuder i grafen \(G\) fra knuden \(v\).

Forklar hvad koden gør.

def BFS(v, G):
    '''
    Afstandsliste fra knude v i graf G.
    '''
    N = len(G.nodes()) # antal knuder i G

    Afstandsliste = [-1]*N # Laver "tom" Afstandsliste af længde N.  
 
    Afstandsliste[v] = 0 # Der er afstand 0 fra v til sig selv.

    # BFS-algoritmen
    for d in range(1,N):
        for i in range(N):
            if Afstandsliste[i] == d-1:
                for j in G.neighbors(i):
                    if Afstandsliste[j] == -1:
                        Afstandsliste[j] = d

    return Afstandsliste

Nedenstående kodecelle viser afstandslisten til knude \(0\).

print('Afstandsliste for knude 0:\n', BFS(0, G))

BFS står for bredde-først-søgning og er en kendt algoritme til at finde korteste stier i en graf.

Prøv at kalde BFS funktionen med en anden knude end knude \(0\) og check at den finder de korrekte afstande.

Nedenstående kode er magen til ovenfor, men nu er der en liste af farver Farveliste.

Tilføj kode således at alle knuder med afstand \(d\) til knude \(v\) får farven Farveliste[d].

def BFS_farver(v, G):
    '''
    Afstandsliste fra knude v i graf G. Farver knuder efter afstand fra v.
    '''
    # liste med farver
    Farveliste = ['red', 'green', 'blue', 'cyan', 'orange', 'purple', 'brown', 'gray',' olive']


    N = len(G.nodes()) # antal knuder i G

    Afstandsliste = [-1]*N   # Laver "tom" Afstandsliste af længde N.

    # Der er afstand 0 fra v til sig selv
    Afstandsliste[v] = 0
    G.nodes[v]['color'] = Farveliste[0]

    # BFS algoritme
    for d in range(1,N):
        for i in range(N):
            if Afstandsliste[i] == d-1:
                for j in G.neighbors(i):
                    if Afstandsliste[j] == -1:
                        Afstandsliste[j] = d
                        # Indsæt kode til farvning
                        
                        ####
                        
    return Afstandsliste

######################
### Farver grafen med BFS_farver
BFS_farver(0, G)

######################
### Tegner grafen
e_colors = [c for u,v,c in G.edges.data('color', default='black')]
n_colors = [c for u, c in G.nodes.data('color', default='blue')]

nx.draw(G, pos=nx.planar_layout(G), edge_color = e_colors, node_color = n_colors, with_labels=True)
plt.show(block=True)

Labyrintopgave#

Nedenstående figur viser en labyrint. Den kan modelleres som en graf ved at lave en knude for hvert felt og en kant mellem to felter hvis man kan gå imellem dem.

I nedenstående kodecelle laver vi en graf med antal knuder, der svarer til alle felterne, men der er ingen kanter.

Kør koden for at se knuderne.

Tilføj kanterne og find længden af den korteste sti fra start til slut.

Labyrint = nx.Graph()

########### Knuder ########
for i in range(36):
    Labyrint.add_node(i)

########### Indsæt kanter her ########


########### Tegner grafen ###########
pos = {}

for i in range(6):
    for j in range(6):
        pos[i + j*6] = (i,j)
print(pos)

nx.draw(Labyrint, pos, with_labels=True)
plt.show(block=True)

Sammenhængskomponenter#

Indtil nu har vi kun kigget på det vi kalder sammenhængende grafer (der findes mindst en sti mellem alle par af knuder). Nedenstående graf er ikke sammenhængende.

Vi siger at to knuder er i samme sammenhængskomponent, hvis der er en sti imellem dem.
Grafen ovenfor har \(4\) sammenhængskomponenter: \(\{2,8,9\}, \{6,7\}, \{0,1,3,5\}, \{4\}\).

I følgende kodecelle defineres en ny graf \(H\).

Kør cellen. Er \(H\) sammenhængende?

H = nx.Graph()
H.add_node(0)
H.add_node(1)
H.add_node(2)
H.add_node(3)
H.add_node(4)
H.add_node(5)
H.add_node(6)
H.add_node(7)
H.add_node(8)
H.add_node(9)
#############################################
### Kanter

H.add_edge(0,1)
H.add_edge(4,6)
H.add_edge(0,8)
H.add_edge(2,3)
H.add_edge(8,5)
H.add_edge(0,5)
H.add_edge(2,9)

##################
### Tegner grafen
nx.draw(H, pos=nx.planar_layout(H), with_labels=True)
plt.show(block=True)

Vi kan bruge BFS til at finde sammenhængskomponenter i en graf.

  • Brug BFS funktionen til at lave en afstandsliste for knude \(0\).

  • Brug derefter afstandslisten til at lave og udskrive en liste hvor der står \(1\) ud for alle knuder der er i samme sammenhængskomponent som knude \(0\) og \(-1\) ud for for alle andre knuder.

#############################################
### Tilføj kode der laver afstandslisten fra knude 0 i graf H



#######################################
## Tilføj kode udskriver en liste hvor der står 1 ud for
## alle knuder der er i samme
## sammenhængskomponent som knude 0.

Opgave: Soløerne#

Adam skal på ferie i øparadiset Soløerne. Der er \(12\) øer og man kan komme mellem øerne ved at sejle med færge eller ved at bruge broer. Adam er ikke glad for at sejle, så han vil gerne vide hvor mange øer han kan besøge uden at sejle, hvis han starter på ø nummer \(5\) (Øboerne var meget uenige om hvem der skulle have lov til at hedde Soløen, så i stedet for at give øerne navne har de nummeret dem fra \(0\) til \(11\)).

Der er færger mellem følgende par af øer:

\[ (0,7), (0,1), (1,10), (2,6), (10,11). \]

Der er broer mellem følgende par af øer:

\[ (4,6), (0,3), (2,5), (1,8), (1,3), (2,9), (3,8), (5,9), (5,10), (6,7), (9,11). \]

Hvor mange øer kan Adam besøge uden at sejle?

Forklar hvordan man kan modellere problemet som en graf og tegn grafen.

Lav kode i boksen nedenfor der løser problemet.

G = nx.Graph()
########## Indsæt knuder her ######


######### Indsæt kanter her ######




####### Indsæt kode der finder ud af hvor mange øer Adam kan besøge ########
####### Husk at du kan bruge BFS funktionen ########





######## Tegner grafen ##################



nx.draw(G, pos=nx.planar_layout(G), with_labels=True)
plt.show(block=True)

Alle sammenhængskomponenter#

Vi kan også bruge BFS til at finde alle sammenhængskomponenterne i en graf. I det følgende vil vi gerne lave en komponentliste for grafen. I komponentlisten skal der stå samme tal ud for \(2\) knuder hvis de er i samme sammenhængskomponent.

Eksempel: Listen \([1, 1, 2, 1, 3, 1, 4, 4, 2, 2]\) er en komponentliste for nedenstående graf.

For at finde alle sammenhængskomponenter bruger vi først BFS til at finde alle knuder der er i samme sammenhængskomponent som knude \(0\). Vi skriver \(1\) ud for dem i komponentlisten. Derefter finder vi en knude der ikke er i samme sammenhængskomponent som knude \(0\) og bruger BFS til at finde alle de knuder der er i dens sammenhængskomponent. Vi skriver \(2\) ud for dem i komponentlisten. Sådan fortsætter vi indtil alle knuder har fået et tal.

Vi vender tilbage til grafen \(H\) som defineret tidligere. Følgende kodecelle genviser grafen.

### Tegner grafen
nx.draw(H, pos=nx.planar_layout(H), with_labels=True)
plt.show(block=True)

Indsæt kode i følgende kodecelle så Komponentliste indeholder alle sammenhængskomponenter for grafen \(H\).

N = len(H.nodes()) # antal knuder i H

### Laver komponentlisten med -1 i alle pladser
Komponentliste = [-1]*N

### For-løkke til at udfylde komponentlisten
for i in range(N):
    if Komponentliste[i] == -1:
        # Afstandsliste fra knude i
        Afstandsliste = BFS(i,H)
        
        ## Skriv kode her, der opdaterer Komponentlisten
        

print("Komponentliste:\n", Komponentliste)

Opgave: Tilbage til Soløerne#

Vi vender tilbage til øgruppen Soløerne. Adam vil stadig helst ikke sejle og vil derfor finde ud af, hvilken ø han skal starte på, så han kan besøge flest muligt øer uden en færgetur.

Indsæt kode i cellen nedenfor, der danner en graf, og bruger den til at løse problemet.

G = nx.Graph()
########## Indsæt knuder her ######

######### Indsæt kanter her ######

######### Indsæt kode der regner ud hvilken ø Adam skal starte på ######

### Tegner grafen
nx.draw(G, pos=nx.planar_layout(G), with_labels=True)
plt.show(block=True)

Adam vil dog helst nå at besøge alle øerne, og han accepterer derfor, at han er nødt til at sejle.

Hvor få gange kan han nøjes med at sejle for at besøge alle øerne? Brug nedenstående kodecelle til at løse problemet.

G = nx.Graph()
########## Indsæt knuder her ######

######### Indsæt kanter her ######

######### Indsæt kode der finder det mindste antal gange Adam er nødt til at sejle ######

### Tegner grafen
nx.draw(G, pos=nx.planar_layout(G), with_labels=True)
plt.show(block=True)
Contents