Graphen und Graphenalgorithmen: Difference between revisions

From Alda
Jump to navigationJump to search
(Gerichteter Graph als Graphik gemacht)
Line 331: Line 331:
=== Tiefensuche in Graphen ===
=== Tiefensuche in Graphen ===


Sei der Graph geg als Liste von Listen = g
Sei der Graph gegeben als Liste von Listen = g


  def dfs (g,node,v=0):
  def dfs (g,node,v=0):
Line 350: Line 350:


=>Folge 1,2,4,3,6,7,5
=>Folge 1,2,4,3,6,7,5


=== Breitensuche ===
=== Breitensuche ===

Revision as of 13:47, 22 June 2008

Einführung zu Graphen

Motivation

Königsberger - Brückenproblem

(1736 Euler)



Königsberger Brücken:

Spaziergang durch Königsberg, so dass alle Brücken nur einmal überquert werden.

Geometrie: Topologie

    O
   || \
   ||  \
    O   O
   ||  /
   || /
    O


  • Definition: ungerichteter Graph

Ein ungerichteter Graph G = ( V, E )

    • V ist endliche Menge von Knoten (vertices)
    • E c V × V (edges)

Ein Graph heißt ungerichtet, wenn zusätzlich gilt:

(x,y) ∈ E => (y,x) ∈ E (symmetrie)

Bsp:

gerichteter Graph gerichteter Graph

ungerichtet

 O
|| \
||  \
 O   O
||  /
|| /
 O



Bsp:

  • Landkarten:
    • Knoten: Länder
    • Kanten: gem. Grenzen
  • Schaltkreis:
    • Knoten: Gatter
    • Kanten: Verbindungen
  • Chemie (Summenformeln):
    • Knoten: Elemente
    • Kanten: Bindungen
  • Soziologie (StudieVZ)
    • Soziogramm
      • Knoten: Personen
      • Kanten: Freund von ...


  • Definition: Vollständige Graphen

Bei vollständigen Graphen ist jeder Knoten mit allen anderen Knoten verbunden.

E = U V (v,w) u (w,v) | v ∈ V, w ∈ V, u != w

k1
k2
k3
k4
k5


Rätsel Auf einer Party sind Leute. Alle stoßen miteinander an. Es hat 78 mal "Pling" gemacht. Wieviele Leute waren da?

Repräsentation von Graphen

Sei G = ( V, E ) geg und liege V in einer lineraren Sortierung vor. V = { v1, ...., vn }

Adjazenzmatrix

AG = aij = {1 falls (vi, vj) ∈ E ; sonst 0}


Bsp:

v = { a,b,c,d }     b      d
                    | \  / |
                    |  \/  |
                    |  /\  |
                    | /  \ |
                    a      c

      a b c d
     -----------
     (0 1 0 1) |a 
AG = (1 0 1 0) |b
     (0 1 0 1) |c
     (1 0 1 0) |d


Adjezenzlisten

al(v) = {v' ∈ V | (u,u') ∈ E} Lg = ((v1, al(v1)), ...., (vn, al(vn))

Python:

Array von Arrays [[...],[...],...,[...]]
                    0     1         n
  • Definition: Teilgraphen

Ein Graph G' = (v',E') ist ein Teilgraph, wenn gilt:

    • v' c V
    • E' c E

Er heißt erzegender Graph, wenn zusätzlich gilt:

    • v' = V


  • Definition: Knotengrade

Für G = (v,E)und v ∈ V grad(v) = |{v' ∈ V | v,v'∈ E}| out_grad(v) = | -""- | in_grad(v) = |{v'∈ V| (v',v) ∈ E}|


Bsp:


ungerichtet

 c
|| \
||  \
 b   d          grad(a) = | {b,b,d} | = 3
||  /
|| /
 a

 
gerichtet

 c←
 | \
 ↓  \
 b←--d         out_grad(d) = 2 = | {c,b} |
 |  /→          in_grad(d) = 1 = | {a} |
 ↓ /
 a
  • Definition: Wege

Sei G = (v,E)

    • Für v0 ∈ V ist (v0) ein Weg in G
    • Für Knoten v1,...vn,vn+1 und eine Kante (vn,vn+1) ∈ E ist mit einem Weg (v0,....vn) in G auch (v0,...,vn,vn+1) ein Weg in G.

Also: Nichtleere Folgen von Knoten die durch eine Kante verbunden sind.


Eulerweg

   O
  /  \
 O----O
 | \/ |
 | /\ |   "Das Haus vom Nikolaus" Alle Kanten werden nur einmal passiert
 O----O


Hamiltonweg

   O
  /   
 O----O
    /  
   /      Alle Knoten werden nur einmal passiert
 O----O


Kreis

   O
  /  \
 O    O
 |    |   v0 = vn
 |    |   vi != vj   Für Alle i,j   i !=j; i,j >0; i,j < n
 O----O     


Zyklen

   O
  /  \
 O    O
   \  |
    \ |   Wie Kreis nur ohne (vi != vj)
 O====O


  • Definition: planare Graphen

Ist ein Graph, der auf einer Ebene gezeichnet werden kann, sodass sich die Kanten nicht schneiden!


Bsp:

1)  

     O
    /|\
   / O \
  / / \ \
  O     O
2)

   O
  /  \
 O----O
 | \/ |
 | /\ |   
 O----O
3)

|----O   @
|   /@ \
|  O----O
|  |@ / |
|  | / @|   
|  O----O               @ entspricht Regionen auch ausserhalb der Figur ist eine Region
|@      |
|-------|


1),2) und 3) sind planare Graphen.


Der K5 Graph ist kein planarer Graph da sich zwangsweise Kanten schneiden.


  • Definition: dualer Graph

Der duale Graph eines geg. planaren Graphs G' ist ein Graph mit

    • Knoten für jede Region
    • Für jede Kante aus E gilt es gibt eine Kante, die die angrenzende Region mit Knoten verbindet.


dualer Graph
     O------O
     |     /| \
   |-|-@  / | @\---|
   | | |\/  |/| O  |
   | | |/\ /| |/   |
   | | /  @ | /    |
   | O-+--+-O |    |
   |   |  |   |    |
   |---|--@---|----|


  • Definition: erreichbar
W ∈ V ist erreichbar von v ∈ G gdw.:
es Existiert Weg(v,...w)


  • Definition: Zusammenhang
G heißt zusammenhängend, wenn für Alle v,w ∈V gilt:
w ist erreichbar von V

Bäume

  • Definition: Baum
Ein Baum ist ein zusammenhängender, kreisfreier Graph.

Bsp.: Binary Search Tree

  • Definition: erzeugender Baum
für G = (v,E) ist ein erzeigender Teilgraph mit Baumeigenschaft

Bsp.:


   O    O
  /    /   
 O    O    O
 |  /    /   
 | /    /    
 O----O----O

Durchlaufen von Graphen

Tiefensuche in Graphen

Sei der Graph gegeben als Liste von Listen = g

def dfs (g,node,v=0):
  if v == 0:
    v = [0]*len(g) #visited-Liste
  v[node] = 1 #besuche node
  for t in g[node]: #gehe zu allen Nachbarn
    if v[t] == 0: #falls diese noch nicht besucht
      dfs(g,t,v) #Rekursion



Aufruf dfs(g,1)

=>Folge 1,2,4,3,6,7,5

Breitensuche

from Queue import *
def bfs(g,startnode)
  v = [0]*len(g)
  q = Queue()
  v = [startnode] = 1 #besuche
  q.put(startnode) #in Schlange
  while not q.get()
    node = q.get()
    for t in q[node]
      if v[t] == 0:
        v[t] = 1
        q.put(t)



=>Folge 1,2,3,4,5,6,7


Damenproblem

 ---------------
|   | X |   |   |
|---|---|---|---| 
|   |   |   | X |
|---|---|---|---|
| X |   |   |   |
|---|---|---|---|
|   |   |   | X |
 ---------------


4 Damen auf einem vereinfachten Schachbrett so Positionieren, dass sich keine bedroht.

erster Durchlauf:


zweiter Durchlauf: