Graphen und Graphenalgorithmen: Difference between revisions

From Alda
Jump to navigationJump to search
(Graphen mit Graphviz gezeichnet --> siehe Talk)
Line 87: Line 87:
E =  U V (v,w) u (w,v)  |  v ∈ V, w ∈ V, u != w
E =  U V (v,w) u (w,v)  |  v ∈ V, w ∈ V, u != w


    K1    |     K2    |    K3    |    K4    |    K5
{| border="0" cellspacing="0" cellpadding="0" style="margin: 1em auto 1em auto"
            |           |            |            | 
|-
            |           |     O      |   O----O  |        O 
| [[Image:k1.png|frame|k1]]
    O      |  O-----O  |    / \    |  | \/ |  |     /| |\
| [[Image:k2.png|frame|k2]]
            |           |   /  \    |   | /\ |  |    / |  | \
| [[Image:k3.png|frame|k3]]
            |           |  O-----O  |  O----O  |  O--|---|--O      (Mit etwas Fantasie erkennt man die Pentagrammähnliche Figur^^)
|-
            |            |           |           |   \ \|  |/ /        (halt 5 Knoten wo jeder mit den anderen 4 verbunden ist)
| [[Image:k4.png|frame|k4]]
            |            |            |           |   \ |   / /
| [[Image:k5.png|frame|k5]]
                                                        \|\ /|/
|
                                                          |/ \|
|}
                                                          O---O     
       


 


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

Revision as of 16:03, 18 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:

gerichtet

O----→O
|     ↑
↓     |
O←----O
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 geg 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: