Klausur

Skalenfreie oder skaleninvariante Netzwerke oder Netze sind komplexe Netzwerke, deren Anzahl von Verbindungen pro Knoten nach einem Potenzgesetz verteilt sind.

1. p*N(N-1) edges

2. E(n) = pN(N-1)/2 (sonst doppelt gezählt?)

verbunden mit P*N

PC(N) is related to the critical probability in percolation theory,

where systems for fixed N have a critical value pC

Percolation probability = prob of a node to belong to the infinite cluster

• p_c = 1/ (z-1)

• Definition: The betweenness of a vertex s is the number of shortest paths between any pair of vertices passing through vertex s

  – If more than one (say n) shortest path exists, then the path passing through s contributes a reduced weight 1/n

  – Paths to vertex s are also counted

Six degrees

-> geringe avagrage distance (smal worls)

Cluster coefficient (Anteil der verbunden Nachbarn / wenn alle verbunden wären)

• Degree Distribution durschnittlicher grad = K

• K^(-y) und y ist fest (mindestems 2)

• bei barabasi albert 3

Das allgemeine Netzwerkflussproblem mit minimalen Kosten ist eine Art Optimierungsproblem, bei dem es darum geht, einen Fluss durch ein Netzwerk zu finden, der die Gesamtkosten des Flusses minimiert und gleichzeitig bestimmte Kapazitätsbeschränkungen erfüllt. Bei diesem Problem erhalten wir einen gerichteten Graphen, der ein Netzwerk darstellt, wobei die Knoten die Standorte und die Kanten die Verbindungen zwischen den Standorten repräsentieren. Jede Kante hat eine Kapazität, d. h. den maximalen Fluss, der durch sie hindurchfließen kann, sowie Kosten, d. h. die Kosten, die entstehen, wenn eine Einheit des Flusses durch die Kante geschickt wird. Der Graph hat auch einen Quellknoten und einen Senkenknoten, die den Start- und Endpunkt des Flusses darstellen. Das Ziel des Problems besteht darin, einen Fluss durch das Netzwerk zu finden, der die Gesamtkosten minimiert und gleichzeitig die Kapazitätsbeschränkungen an jeder Kante beachtet. Dieser Fluss sollte am Quellknoten beginnen und am Senkenknoten enden, und er sollte die folgenden Beschränkungen erfüllen: Flusserhaltung: An jedem Knoten muss der Gesamtfluss, der in den Knoten eintritt, gleich dem Gesamtfluss sein, der den Knoten verlässt, außer an den Quell- und Senkenknoten. Kapazitätsbeschränkungen: Der Fluss durch eine Kante darf die Kapazität dieser Kante nicht überschreiten. Nicht-Negativität: Der Fluss durch eine beliebige Kante muss nicht negativ sein. Die Lösung des allgemeinen Netzwerkflussproblems mit minimalen Kosten erfordert die Suche nach einem Gleichgewicht zwischen der Minimierung der Kosten des Flusses und der Sicherstellung, dass die Kapazitätsbeschränkungen erfüllt werden. Dies kann mit Algorithmen wie dem Simple Minimum Cost Flow Algorithmus oder dem Network Simplex Algorithmus geschehen. Ein Co-Tree ist eine baumartige Struktur, die die Konnektivität eines Flussnetzes darstellt. Er wird aus dem Flussnetzwerk abgeleitet, indem die Kanten, die keinen Fluss tragen, kontrahiert und die Kanten, die einen Fluss tragen, expandiert werden. Die sich daraus ergebende Baumstruktur wird als Co-Baum bezeichnet, weil sie das "Komplement" des Flussnetzes darstellt, in dem Sinne, dass sie die Struktur des Netzes anhand der Kanten zeigt, die keinen Fluss tragen.

1. Ford-Fulkerson: Terminiert im Worst-Case nicht.

2. Edmond-Karp: O(n*m*m)

3. Preflow-Push: O(n*n*n)

Das Max-Flow-Min-Cut-Theorem ist ein grundlegendes Ergebnis bei der Untersuchung von Flussnetzwerken. Es besagt, dass in jedem Flussnetz der maximale Fluss von der Quelle zur Senke gleich der minimalen Kapazität des Schnitts ist, die als die Gesamtkapazität der Kanten definiert ist, die entfernt werden müssen, um die Quelle von der Senke zu trennen.Beim Max-Flow-Min-Cut-Problem geht es darum, den maximalen Fluss, der durch ein Flussnetz übertragen werden kann, sowie den entsprechenden minimalen Cut zu finden. Dieses Problem kann mit einer Reihe von Algorithmen effizient gelöst werden, darunter der Ford-Fulkerson-Algorithmus und der Dinic-Algorithmus.Eine Anwendung des Max-Flow-Min-Cut-Theorems findet sich in der Bioinformatik, wo es zur Modellierung des Informationsflusses durch biologische Netzwerke verwendet werden kann. So kann es beispielsweise zur Analyse des Flusses genetischer Informationen durch ein Netzwerk von Genen und regulatorischen Elementen oder zur Modellierung des Flusses von Signalmolekülen durch ein Netzwerk von Signalwegen verwendet werden.Neben seinen Anwendungen in der Bioinformatik hat das Max-Flow-Min-Cut-Theorem eine Vielzahl von Anwendungen in der Informatik und im Ingenieurwesen, einschließlich der Gestaltung von Kommunikationsnetzen, der Planung von Ressourcen und der Analyse von Transportsystemen.

Bellman-Ford und Dijkstra sind beide Algorithmen zur Bestimmung des kürzesten Weges zwischen zwei Knoten in einem gerichteten oder ungerichteten Graphen mit Kantengewichten.

Der Dijkstra-Algorithmus ist ein Greedy-Algorithmus, der den kürzesten Weg von einem Startknoten zu allen anderen Knoten des Graphen berechnet. Der Algorithmus arbeitet schrittweise und wählt in jedem Schritt den am nächsten gelegenen unbesuchten Knoten aus, um den Pfad zum nächsten Knoten zu aktualisieren. Dieser Prozess wird so lange fortgesetzt, bis alle Knoten besucht wurden.

Im Gegensatz dazu ist der Bellman-Ford-Algorithmus ein Algorithmus zur Bestimmung des kürzesten Pfades von einem Startknoten zu allen anderen Knoten in einem Graphen, der auch negative Kantengewichte zulässt. Der Algorithmus arbeitet schrittweise und aktualisiert den Pfad zum Zielknoten durch Überprüfen aller Kanten im Graphen und Aktualisieren des Pfades, falls eine kürzere Route gefunden wurde. Dieser Prozess wird so lange fortgesetzt, bis alle Pfade aktualisiert wurden oder ein negativer Zyklus gefunden wurde.

In Bezug auf die Laufzeit sind Dijkstra und Bellman-Ford Algorithmen sehr unterschiedlich. Die Laufzeit des Dijkstra-Algorithmus beträgt O(|E|+|V|log|V|), wobei |V| die Anzahl der Knoten im Graphen und |E| die Anzahl der Kanten ist. Der Bellman-Ford-Algorithmus hat eine Laufzeit von O(|V||E|), was in der Praxis langsamer sein kann, aber im Gegensatz zu Dijkstra auch mit negativen Kantengewichten umgehen kann.

Insgesamt hängt die Wahl des Algorithmus davon ab, ob der Graph negative Kantengewichte hat oder nicht. Wenn es keine negativen Kantengewichte gibt, ist Dijkstra aufgrund seiner schnelleren Laufzeit die bessere Wahl. Wenn es jedoch negative Kantengewichte gibt, ist Bellman-Ford der einzige Algorithmus, der eine korrekte Lösung liefert.

A percolation point is a point at which water can flow from the top of the grid to the bottom of the grid. One way to find the percolation point for a given permutation is to use the following algorithm:

1. Set all cells in the grid to be blocked (not percolated).

2. Iterate through the permutation, setting each cell to be open (percolated) in the order specified by the permutation.

3. For each open cell, check if it is connected to an open cell at the top of the grid. If it is, mark it as part of the percolation cluster.

4. Repeat step 3 for each open cell until all open cells have been checked.

5. If there are any open cells that are part of the percolation cluster and are also at the bottom of the grid, then the percolation point has been reached. Return the coordinates of the percolation point.

The running time of this algorithm is O(N^2) because it involves iterating through the grid and checking each cell. The check_top_connection function is called recursively for each cell, but the number of recursive calls is limited by the size of the cluster.

Durchschnittlicher Cluster Koeffizient für Knoten mit k Nachbarn Scale free: C(k) constant und hirachisch C(k) = k ^-1 = 1/k

• hat Eigenschaften von regular Lattices (hohes Clustering) aber auch Eigenschaften von Random Netzwerken (small world)

• man fügt in jedem Schritt einen neuen Knoten zum Graphen hinzu (Growth) und eine Kante zwischen dem neuen Knoten und einem bereits vorhandenen Knoten wird mit Wahrscheinlichkeit Pi(k) = k_i / sum(k_j) initialisiert. (k_i sind die degrees) Preferential Attachment

1. gamma = 3

1. gamma >= 2

1. erste Moment = unendliche Summe(k*p(k)) = unendliche Summe(k*k^(-gamma)) konvergiert nur für gamma >= 2.

1. Zu jedem Zeitschritt werden ein Knoten und eine Kante hinzugefügt. Dabei ist die Wahrscheinlichkeit für einen Knoten (der zum Zeitpunkt s eingefügt wurde) einen link (ein Ende einer Kante) zu erlangen:

1. P(s, t) = 2 * (k(s,t) + A) / (sum(k(s,t)+A)) = 2 * (k + A / (t*(2+A)))

1. A ist notwendig, damit auch Knoten mit Grad 0 einen Link erhalten können.

1. Die Randbedingung lautet: P(s=t,t) = 0

2. Es resultiert eine Knotengrad-Verteilung mit Power-Law-Koeffizienten gamma >= 2.

1. NDEx bietet eine Datenbank für Netzwerke aller Art an, Cytoscape/TopNet ermöglichen eine Kombination von Expressionsdaten und Netzwerken zum Beispiel für Pathway-Analysen.

1. Die Anzahl der Knoten (N) ist NICHT festgelegt. - Netze erweitern sich ständig durch das Hinzufügen neuer Knotenpunkte. - z.B. WWW, Veröffentlichung von neuen Dokumenten 2. Die Verknüpfung ist NICHT gleichmäßig. - Ein Knoten ist mit höherer Wahrscheinlichkeit mit einem Knoten verbunden, der bereits eine große Anzahl von Verknüpfungen hat. - Beispiele: WWW: neue Dokumente werden mit bekannten Seiten verlinkt (CNN, YAHOO, NewYork Times, Zitierung: gut zitierte Dokumente werden mit größerer Wahrscheinlichkeit erneut zitiert.

occurrence sequenz ist endlich

- Eine Markierung M in einem Petrinetz (N, M_0) ist abdeckbar, wenn es eine Markierung M' in R(M_0) gibt, so dass M'(p) >= M(p) für jedes p im Netz - Überdeckbarkeit ~ L1-Lebensfähigkeit - Wenn M die minimale Markierung ist, die benötigt wird, um den

Übergang t zu ermöglichen, dann - t ist tot (nicht L1-live), wenn M nicht abdeckbar ist - t ist L1-live, wenn M abdeckbar ist

- Metrik (d(x,x)=0, d(x,y) >= 0, Dreiecksungleichung) - Misst die gegenseitige Abhängigkeit zwischen zwei Ereignissen (Transitionen) - Der synchrone Abstand zwischen zwei Transitionen t1 und t2 in einem Petrinetz (N,

M_0) durch wobei s eine Feuerungssequenz ist, die bei einer beliebigen Markierung M in R(M_0) beginnt, und |s(t)| die Anzahl der Feuerungen von t in s ist

- Begrenzte Fairness (B-fair) - Zwei Übergänge sind begrenzt fair, wenn die maximale Anzahl, die einer der beiden Übergänge auslösen kann, während der andere nicht auslöst begrenzt ist - Ein Petrinetz ist begrenzt fair, wenn jedes Paar von Übergängen begrenzt fair ist. - Unbedingte, globale Fairness - Eine Feuerungssequenz s ist (bedingungslos) global fair, wenn sie endlich ist oder jeder Übergang im Netz unendlich oft in s vorkommt - Ein Petrinetz ist (bedingungslos) global fair, wenn jede Abschussfolge Sequenz aus einer erreichbaren Markierung M in R(M_0) global fair ist - Relation ? - Jedes B-faire Netz ist global fair - Jedes beschränkte global faire Netz ist B-fair - Es gibt (unbeschränkte) global faire Netze, die nicht B-fair sind

Siphon: einmal leer -> immer leer

Trap: einmal markiert -> immer markiert

jede erreichbare MArkierung ermöglicht sdchlaftung einer transition

wenn spanning tree gegeben

-> färben nach Ebenen in abwechslenen Farben -> wenn man eine Kante zum spanning tree hinzufügtb -> cycle

jede errrecihbare markierung ermöglicht schaltung einer occurence seq die alle transitionen enthält

• L0: wenn die transition in keiner Feuersequenz gefeuert werden kann

• L1: wenn die transition in mindestens einer Feuersequenz gefeuert

  werden kann

• L2: wenn die transition in mindestens einer Feuersequenz gefeuert k

  mal werden kann (mit einer anderen Transition state k mal aufpumpen)

• L3: in einer Feuersequenz kommt die Transition unendlich oft vor

• L4: die transition kann aus jeder erreichbaren Markierung gefeuert

  werden

zwei events könnten schalten weil sie die gleiche condition haben

tansitionen schalten abwecheslnd

ein event schalten vor conflict

zwei transitionen projezieren auf ein state

N*t=0

N^t*s = 0

Tiefensuche

in O(m+n)

Anwendung: topo Ordnung, SCC finden

Breitensuche

in O(m+n)

shortest paths finden

Matrix multiplizieren mit k -> walks der länge k

alle Knoten ohne Nachfolger beschriften

-> alle Knoten bei denen alle Nachfolger beschriftet sind beschriften

KNoten markieren

• + wenn man hinkommt

• - wenn man weg kommt

-> drei Kategorien, +, -, +-

comp(v) markieren

wie mit +, -, +-

O(n+m)

proper -> graph noch connected wenn man Knoten entfernen kann

nicht proper -> normale schleife: löschen von Knoten kann ganzen zyklus vom Graphen trennen ABER trotzdem ist der Graph 2-edge-connected WEIL man kante entfernen könnte

Immer die kleinste Kante hinzufügen

• greedy

• minimal spannbaum

• ungerichteter graph

Laufzeit

• sortiere-> O(m log m)

• m mal prüfen ob circuit -> O(mn)

entfernen paraleler kanten o(n^2)

kann fast linear gemacht werden

bei einem beliehbigen Knoten starten

-> immer die kleinste Kante die dran hängt hinzufügen

O(n^2)

WEIL kleinste Kante finden in n und das macht man n mal

O(m) in planaren graphen

MWA wie spanning tree nur gerichtet

Laufzeit O(mn)

fibonacci heaps -> O(m + n log n)

Grundidee:

Circuits zu Knoten weil man davon am ende nur eine kante rausschmeißt und den rest braucht

-> in ebenen die Kreise rausschmießen; i bleibrt klein -> laufzeit gering

O(M*N)

Single source

ähnoiche wie dikstra

FALSE wenn Zyklus mit negaitven Gewicht

directed azyklisch

lösbar in linearer Zeit O(m+n)

topologische ordnung-> reLAX (umwege zu eimem Pfad machen wenn sie kürzer sind )

O(n^2) bzw fibo-heaps O(n log n + m)

single source shortest paths

keine neg kanten

durch den grphen gehen immer den kürhzesten Pfad zu dem Knoten merken und updaten

all pairs shortest paths

directed graph

O(n^3)

immer dreieck prüfen was der kürzeste weg ist

(ist der Umweg über anderne Knoten kürzer?)

dreieck -> drei mal über alle Knoten laufen

Der Algorithmus beruht auf der Idee, einen Weg von der Quelle zur Senke zu finden, entlang dessen der Fluss weiter vergrößert werden kann, ohne die Kapazitätsbeschränkungen der Kanten zu verletzen. Ein solcher Weg wird auch als augmentierender Pfad bezeichnet. Durch Wiederholung können die Flüsse entlang mehrerer solcher Wege zu einem noch größeren Gesamt-Fluss zusammengefasst werden. Wird stets der kürzeste Weg gewählt, ergibt sich der Edmonds-Karp-Algorithmus.

maximalen fluss finden

argumenting paths verwenden um flow zu vergößern

Tiefensuche im graphen bis residual graph keine kapazitöt ,mehr

Problem Laufzeit -> termininiert manachmal gar nciht

abhängig vom flow

Ford Fulkerson aber in jedem schritt den kürzesten argumemnting graoh finden mit BFS

O(n*m^2)

max flow berechnen

chnage preflow on edge by edge basis

von einem Knoten einen Pfad zu allen anderen Knoten suchen

geht für gerichtete und ungerichtete Graphen

arboreszenz

Induktionsbweis:

azyklisch -> es gibt einen Knoten ohne Vorgänger -

Induktionsschluss: Graph ohne zusätzliches v hat Ornung

-> sortierung ergibt sich durch ord(v’)=ord(v’)+1