Proseminar „Algorithmen auf Graphen"

Proseminar „Algorithmen auf Graphen"

Proseminar Algorithmen auf Graphen Zuflliges Erzeugen von Graphen und Bayes-Netzen Bjrn Schapitz, CV04, 20.06.2006 Gliederung (1) (2) (3) Einleitung Geschichtliches Algorithmen / Beispiele (1) (2) (3) (4) (5) (4)

(5) 2 Anschauliches Vorgehen Zufllige Adjazenzmatrix Zufllige Kantenanordnung Rekursive Erzeugung One-Pass-Algorithm Zufllige Bayes-Netze Zusammenfassung Grnde zur Beschftigung mit zuflligen Graphen 1. Beweise fhren (Nachweise der Existenz von Graphen mit bestimmten Eigenschaften) 2. Modellierung von groen, unberschaubaren Strukturen (z.B. Netzwerke, Internet) 3

Einleitung Arten zuflliger Graphen echt zufllige Graphen Oft bestimmte Eigenschaften bentigt: 4 Begrenzt maximale Cliquen Verhltnis Kanten/Knoten (Dichte) Zusammenhngend ? Geschichtliches Paul Erds

5 ungarischer Mathematiker * 26.03.1913, 20.09.96 Entwickelte die Probabilistische Methode zum Beweis seines Satzes: Es gibt Graphen, die gleichzeitig beliebig hohe Taillenweite und beliebig hohe chromatische Zahl haben. Anschauliches Vorgehen 6

Leeren Graphen mit n Knoten erzeugen Wahrscheinlichkeitszahl p mit 0 p 1erzeugen Fr jedes Tupel (n1,n2) mit (n1n2) entscheiden, ob Kante gesetzt wird Beispiel: Zufllige Adjazenzmatrix n Knoten: n x n Matrix erzeugen Mit Nullen fllen Wahrscheinlichkeitszahl p erzeugen: 0 p 1 Fr jedes Element der oberen Dreiecksmatrix (ohne Hauptdiagonale): 7

Zufallszahl x erzeugen: 0 x 1 Wenn x > p, Element auf 1 setzen Beispiel 1 8 Zufallsgraph mit 5 Knoten 5 x 5 Matrix erzeugen n1 n2 n3 n4 n5 n1

0 0 0 0 0 n2 0 0 0 0 0

n3 0 0 0 0 0 n4 0 0 0 0 0

n5 0 0 0 0 0 Beispiel 1 Wahrscheinlichkeit p erzeugen p = 0.5 Fr jedes Element oberhalb

der Hauptdiagonalen Zufallszahl x erzeugen falls x > p, Matrixelement anpassen n1 n2 n3 n4 n5 n1 0 1 0 1 1 n2 0 0 1 1 0 n3 0 0 0 0 1 n4 0 0 0 0 1 n5 0 0 0 0 0 9 Beispiel 1 Graph anhand Adjazenzmatrix aufbauen n1 n2 n3 n4 n5 10 n1 0

1 0 1 1 n2 0 0 1 1 0 n3 0 0

0 0 1 n4 0 0 0 0 1 n5 0 0 0 0

0 Eigenschaften so erzeugter Graphen 11 Erzeugt echt zufllige Graphen Anzahl der Kanten ber p beeinflussbar Nicht immer zusammenhngend Komplexitt: O(n2) Zufllige Kantenanordnung Leeren Graphen mit n Knoten erzeugen Anzahl der Kanten e zwischen 0 und emax whlen

1 bis e mal: 12 p und q von 1..n whlen, so dass p

(max. Anzahl Kanten ohne Loops = (n(n-1))/2 e zufllig aus 1 bis 10: e = 8 Beispiel 2 1 bis 8 mal p und q aus 1..n whlen (mit p

p=2 q=5; Eigenschaften so erzeugter Graphen gezieltes Setzen von e = feste Kantenanzahl Durch geeignete Wahl von p und q kann die max. Anzahl der Eltern und Kinder beeinflusst werden Sind nicht immer zusammenhngend Laufzeit: abhngig von e Komplexitt: bis zu O(n2) 15 Rekursive Erzeugung 16

Basiert auf der Formel von R.W. Robinson, Anzahl mglicher Graphen mit n Knoten und k Wurzeln ist an(k), mit Wiederholte rekursive Zerlegung in Wurzeln und Rest-Knoten Fr alle mglichen Wurzel-Anzahlen s des Teilgraphen alle Kombinationen aufsummieren Rekursive Erzeugung - Algorithmus - 1. 2. Umkehrung der Berechnungsformel zur Berechnung eines Graphen (bentigt Knotenmenge V und Wurzelanzahl k) Zufllig k Wurzeln whlen: K V, |K| = k Zufllig s aus 1..(n-k) whlen, dabei beachten: (s wird fr die Erzeugung von S

17 V\K bentigt) Rekursive Erzeugung - Algorithmus 3. 4. 5. Whle zufllig und unabhngig voneinander s nichtleere Teilmengen aus K Eltern fr jedes Element aus S Whle zufllig und unabhngig voneinander (n-k-s) Teilmengen (drfen leer sein) aus K Eltern fr Elemente aus V\K\S Benutze diesen Algorithmus rekursiv, um aus V \ K als Knotenmenge und s als Anzahl der Wurzeln einen azyklischen Graphen mit den Wurzel-Knoten S zu erzeugen Bei zuflliger Bestimmung von k muss P(k)=an(k)/an gelten. 18

Rekursive Erzeugung - Eigenschaften Vorteile: Nachteile: 19 Variation von k und s hoher/breiter Graph Rekursive topologische Aufspaltung einfacheres Ermitteln von Attribut-Abhngigkeiten Nicht immer zusammenhngend an(k) mssen fr alle Kombinationen von k und n berechnet

und zwischengespeichert werden (a1=1, a2=3, a3=25, , a7=1.138.779.265!!!) Komplexitt: O(n2) One-Pass-Algorithm Erzeugt in einem Schritt einen zusammenhngenden Graphen Anzahl Knoten n und Wurzeln r muss bekannt sein Maximaler Eingangsgrad m ist begrenzt 20 One-Pass-Algorithm Notwendige 21

Bedingungen: n 2 sinnvoller Graph muss mindestens 2 Knoten haben 1 r < n mindestens eine Wurzel 1 m < n zusammenhngender Graph One-Pass-Algorithm Einschrnkungen von n, r und m: wenn r m, dann m(n-r) n-1 sonst m(n-r) + m(m-1)-r(r-1) n-1 2

22 Eingabe: Knoten n, Wurzeln r und maximaler Eingangsgrad m Ausgabe: zusammenhngender azyklischer gerichteter Graph Komplexitt: O(mn) One-Pass-Algorithm Maximale Kantenanzahl berechnen: emax = m(n-r) falls r m

emax = m(n-r)+(m(m-1)-r(r-1)) sonst Kantenanzahl e zufllig aus Intervall [n, emax] bestimmen Fr alle Wurzelknoten (v0vr-1) Eingangsgrad d-(vi)=0 setzen Fr restliche Knoten d-(vi) = [1,min(i,m)] setzen dabei beachten, dass i=r d-(vi)=e sein muss 23 One-Pass-Algorithm Fr alle Knoten Anzahl zu verbindender Eltern p(vi)=d-(vi) Fr i=r bis n-1:

Fr i=0 bis r-2 Kante von vj zu vi setzen (j [r-1,i-1]) Kante von vi zu x setzen (x {vvj | p(vj)1})) Fr i=r bis n-1: Solange p(vi) 1 wiederhole: 24 Kante von x zu vi setzen (x {vvj | 0 j i-1, (vj,vi) E})) Beispiel 3

Graph mit 5 Knoten, 2 Wurzeln und maximalem Eingangsgrad 2 Bedingungen: 25 n 2 erfllt 1 r < n erfllt 1 m < n erfllt Einschrnkung: da r m, muss m(n-r) n-1 gelten 2(5-2) 5-1 6 4 Beispiel 3 1.

2. 3. 4. emax = m(n-r) = 6 e=6 d-(n0)=0, d-(n1 )=0 restliche Knoten: n2=[1,min(2,2)]=2 n3=[1,min(3,2)]=2 n4=[1,min(4,2)]=2 5. p(n2)=2 26 p(n3)=2 p(n4)=2

Beispiel 3 6. i=2 bis 4 nj ni, j[1,1] n1 n2 nj ni, j[1,2] n1 n3 nj ni, j[1,3] n1 n4 7. i=0 bis 0 27 Kante von ni zu x, wobei x={vnj | p(nj)1}) n0 n2 Beispiel 3

8. i=2 bis 4 p(n2) 1 ? nein p(n3) 1 ? ja, x zu n3, x {vnj | 0 j 2, (nj,n3) nicht Element von E nj=n0, n0n3 p(n4) 1 ? ja, x zu n4, x {vnj | 0 j 3, (nj,n4) nicht Element von E nj=n0, n0n4 28 Bayes-Netze Bayessches 29 Netz: Gerichteter azyklischer Graph Jeder Knoten besitzt Variable mit Angabe ber

ihre statistische Verteilung Meistens zusammenhngend Erweitern zum Bayesschen-Netz 30 Jedem Knoten vi Variable Vi zuordnen Anzahl der mglichen Zustnde fr Vi bestimmen: Ni=|Vi| Fr jeden Wurzelknoten: Ni Zufallswerte erzeugen und zu =1 normieren Fr alle anderen Knoten in topologischer Reihenfolge: fr jede Belegung der Elternknoten Ni Zufallswerte erzeugen und zu =1 normieren Bei Bedarf beliebig viele Einzelbelegungen des Netzes

entsprechend den Verteilungen erzeugen Komplexitt: abhngig von Elternknoten-Anzahl, O(mn) Zusammenfassung 31 Zufllige Graphen verwendet zur Beweisfhrung und zur Modellierung unbersichtlicher Strukturen Algorithmen: Zufllige Adjazenzmatrix: kaum Variationen mglich Zufllige Kantenzuordnung: Variationen bedingt ber Parameter mglich Rekursive Erzeugung: Struktur variierbar, aber komplex und langsam One-Pass-Algorithm: zusammenhngend, wenige Kanten

gut fr Bayessche-Netze Bayessche Netze: Erweiterungen obiger Algorithmen mit Zustandsvariablen fr Knoten Quellen 32 Reinhard Diestel: Graphentheorie, 1996, Springer Svante Janson, Tomasz Luczak, Andrzej Rucinski: Random Graphs, 2000, John Wiley & Sons Inc. Lothar Wenzel: Wie klein ist doch die Welt, in: Toolbox, Ausgabe 6/2002, S. 6 ff. Ansgar Voigt: Mathe-Tricks in der Biologie, in:

RUBIN, 2003 Peter Eichelsbacher: Die Steinsche Methode, 2003

Recently Viewed Presentations

  • The Shapes of Orbitals:

    The Shapes of Orbitals:

    Energy Level Diagram for a Multi-Electron Atom Shell Orbitals having the same n value (same floor in a hotel) For n = 2, the shell consists of one 2s orbital, and three 2p orbitals For n = 3, the shell...
  • Density-Driven Downwelling and Thermohaline Circulation Motion of the

    Density-Driven Downwelling and Thermohaline Circulation Motion of the

    is the density-driven circulation of the ocean below the pycnocline. both . temperature. and . salinity. are important in the production of bottom, deep, and intermediate water masses. p. 144. Intermediate, Deep, & Bottom Water Masses.
  • Parenting Wisdom - Proverbs 2 - Grace Bible College

    Parenting Wisdom - Proverbs 2 - Grace Bible College

    In the final analysis this is achieved through discipline as clearly taught in the Proverbs. We have found that authority must be established early, preferably before the child is five; however, it will continue through the early years of childhood....
  • White Pine Decline in Maine

    White Pine Decline in Maine

    Department of Forest Ecosystem Science University of Maine ... Plow pans Soil compaction Old fields favored white pine Rooting restrictions Land Use History Harvard Forest Diorama Livingston et al. 2005 Livingston et al. 2005 Steve Howell, 2000 Brown and Lacate,...
  • 26.3 Birds TEKS 7A, 7B, 10A The student

    26.3 Birds TEKS 7A, 7B, 10A The student

    Times MS Pゴシック Arial Calibri Blank Presentation 1_Blank Presentation The student is expected to: 7A analyze and evaluate how evidence of common ancestry among groups is provided by the fossil record, biogeography, and homologies, including anatomical, molecular, and developmental; 7B...
  • Choosing activities for Core Learning in Mystery of

    Choosing activities for Core Learning in Mystery of

    Visits to Church , processions, knowledge of vestments, penitential services. helping prepare for the Sacrament of Reconciliation should be arranged. Core learning on Mass will gradually increase awareness of the Liturgy of the Word, and . Liturgy of the Eucharist...
  • Association between Obesity predisposing Genes and Adiposity ...

    Association between Obesity predisposing Genes and Adiposity ...

    Association between Obesity predisposing Genes, Energy intake and Adiposity in Early Life: preliminary results from CHILD and START cohorts. Marie Pigeyre. Post-doc fellow (worksupervised by Dr D. Meyre)
  • Chapter 5: Managerial Ethics &amp; Corporate Social Responsibility

    Chapter 5: Managerial Ethics & Corporate Social Responsibility

    Criteria for Ethical Decision Making Social Responsibility Corporate Actions Toward Social Demands Code of Ethics Ethics The code of moral principles and values that govern the behaviors of a person or group with respect to what is right or wrong....