{"id":4295,"date":"2019-05-29T14:01:37","date_gmt":"2019-05-29T13:01:37","guid":{"rendered":"http:\/\/roboblog.fatal-fury.de\/?p=4295"},"modified":"2019-06-08T11:00:26","modified_gmt":"2019-06-08T10:00:26","slug":"graph","status":"publish","type":"post","link":"http:\/\/roboblog.fatal-fury.de\/?p=4295","title":{"rendered":"Graph - Basic graph definitions"},"content":{"rendered":"<p>Shortcut links:<br \/>\nBasic graph definitions (this page)<br \/>\n<a href=\"http:\/\/roboblog.fatal-fury.de\/?p=4378\">Basics of shortest paths<\/a><\/p>\n<h2>Gerichtete und ungerichtete Graphen<\/h2>\n<ol>\n<li>Ein <b>gerichteter Graph<\/b> &#x1D43A; = (&#x1D449;, &#x1D434;) besteht aus einer endlichen Menge &#x1D449; von <b>Knoten<\/b> und einem multiset &#x1D434; von <b>geordneten<\/b> Paaren von Knoten. Die Elemente von &#x1D434; sind die <b>gerichteten Kanten<\/b> von &#x1D43A;.<\/li>\n<li>Ein <b>ungerichteter Graph<\/b> &#x1D43A; = (&#x1D449;, &#x1D438;) besteht aus einer endlichen Menge &#x1D449 von <b>Knoten<\/b> und ein multiset &#x1D438; von <b>ungeordneten<\/b> Paaren von Knoten. Die Elemente von &#x1D438; sind die <b>ungerichteten Kanten<\/b> von &#x1D43A;.<\/li>\n<li>Ein gerichteter oder ungerichteter Graph ist <strong>simple<\/strong> (einfach), wenn:\n<ul>\n<li> Kein Knoten, in &#x1D434; oder &#x1D438;, mit sich selbst verbunden ist<\/li>\n<li> Die multisets &#x1D434; oder &#x1D438; sind nur sets<\/li>\n<\/ul>\n<\/li>\n<li>Ein gerichteter Graph &#x1D43A; = (&#x1D449;, &#x1D434;) ist\n<ul>\n<li><strong>symmetrisch<\/strong>, wenn (&#x1D463;,&#x1D464;) &isin; &#x1D434; impliziert (&#x1D464;,&#x1D463;) &isin; &#x1D434;<\/li>\n<li><strong>anti-symmetrisch<\/strong>, wenn (&#x1D463;,&#x1D464;) &isin; &#x1D434; impliziert (&#x1D464;,&#x1D463;) &notin; &#x1D434;<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<h2>Adjacency, incidence, degree (benachbart, verbunden, Grad)<\/h2>\n<ol>\n<li>Zwei Knoten eines gerichteten oder ungerichteten Graphen hei\u00dfen <strong>adjacent<\/strong> (benachbart), wenn sie mindestens eine gemeinsame Kante haben.<\/li>\n<li>Ein Knoten und eine Kante hei\u00dfen <strong>incident<\/strong> (verbunden), wenn der Knoten zu der Kante geh\u00f6rt.<\/li>\n<li>Zwei Kanten hei\u00dfen <strong>incident<\/strong> (verbunden), wenn sie mindestens einen gemeinsamen Knoten haben.<\/li>\n<li>F\u00fcr einen Knoten, die Anzahl der incident (verbundenen) Kanten ist der <strong>Grad<\/strong> von diesem Knoten. Ein Knoten mit Grad 0 hei\u00dft isoloert.<\/li>\n<li>Betrachte einen gerichteten Graph &#x1D43A; = (&#x1D449;, &#x1D434;):\n<ol>\n<li>F\u00fcr eine Kante &#x1D44E; = (&#x1D463;,&#x1D464;) &isin; &#x1D434;, &#x1D463; ist der <strong>tail<\/strong> (Fu\u00df,Startknoten) von &#x1D44E; und &#x1D464; ist der <strong>head<\/strong> (Kopf\/Endknoten) von &#x1D44E;.<\/li>\n<li>Eine Kante &#x1D44E; = (&#x1D463;,&#x1D464;) &isin; &#x1D434; ist eine <strong>outgoing<\/strong> (abgehende) Kante von &#x1D463 und eine <strong>incoming<\/strong> (eingehende) Kante von &#x1D464;.<\/li>\n<li><strong>outdegree<\/strong> von einem Knoten &#x1D463; &isin; &#x1D449 ist die Anzahl der abgehenden Kanten.<\/li>\n<li><strong>indegree<\/strong> von einem Knoten &#x1D463; &isin; &#x1D449 ist die Anzahl der eingehenden Kanten.<\/li>\n<\/ol>\n<\/li>\n<\/ol>\n<h2>Transpose of a graph<\/h2>\n<p>F\u00fcr einen gerichteten Graph &#x1D43A; = (&#x1D449;, &#x1D434;), die <strong>transpose<\/strong> (Vertauschung) von &#x1D43A; ist das Ergebnis vom Drehen aller Kanten von &#x1D43A;. (Start- und Zielknoten tauschen)<\/p>\n<h2>Subgraph <\/h2>\n<ol>\n<li>Gegeben sind zwei <strong>einfache, ungerichtete<\/strong> Graphen &#x1D43A;<sub>1<\/sub> = (&#x1D449;1, &#x1D438;1) und &#x1D43A;2 = (&#x1D449;2, &#x1D438;2).<br \/>\nDann ist &#x1D43A;1 ein <strong>subgraph<\/strong> von &#x1D43A;2, wenn es eine Knotenteilmenge &#x1D449' &sube; &#x1D449;2 gibt und eine bijektive (umkehrbare) Funktion &phi;: &#x1D449;1 -> &#x1D449' gibt, welche alle Knoten aus &#x1D449;1 auf die Teilmenge &#x1D449' von &#x1D449;2 abbildet, und zwar genau so, dass eine Kante {&#x1D463;,&#x1D464;} aus &#x1D438;1 impliziert, dass es eine andere Kante {&phi;(&#x1D463;),&phi;(&#x1D464;)} &isin; &#x1D438;2 gibt.<br \/>\nDenn es m\u00fcssen nicht nur alle Knoten von &#x1D449;1 in &#x1D449;2 zu finden sein, sondern nat\u00fcrlich auch alle Kanten.<\/li>\n<li>Gegeben sind zwei <strong>einfache, gerichtete<\/strong> Graphen &#x1D43A;<sub>1<\/sub> = (&#x1D449;1, &#x1D434;1) und &#x1D43A;2 = (&#x1D449;2, &#x1D434;2).<br \/>\nDann ist &#x1D43A;1 ein <strong>subgraph<\/strong> von &#x1D43A;2, wenn es eine Knotenteilmenge &#x1D449' &sube; &#x1D449;2 gibt und eine bijektive (umkehrbare) Funktion &phi;: &#x1D449;1 -> &#x1D449' gibt, welche alle Knoten aus &#x1D449;1 auf die Teilmenge &#x1D449' von &#x1D449;2 abbildet, und zwar genau so, dass eine Kante (&#x1D463;,&#x1D464;) aus &#x1D434;1 impliziert, dass es eine andere Kante (&phi;(&#x1D463;),&phi;(&#x1D464;)) &isin; &#x1D434;2 gibt.<br \/>\nQuasi das selbst wie f\u00fcr ungerichtete Grapen.<\/li>\n<li>Ein <strong>spanning<\/strong> subgraph von einem ungerichteten oder gerichteten Graphen &#x1D43A; ist ein subgraph welcher alle Knoten von &#x1D43A; enth\u00e4lt.<br \/>\nAber nicht alle Kanten (es bildet sich ein Baum).<\/li>\n<\/ol>\n<h2>Paths<\/h2>\n<ol>\n<li>Ein <strong>ordinary<\/strong> (gew\u00f6nlicher) Path in einem <strong>ungerichteten<\/strong> Graphen ist eine endliche, geordnete Sequenz ({v<sub>1<\/sub>,v<sub>2<\/sub>}, {v<sub>2<\/sub>,v<sub>3<\/sub>}, ..., {v<sub>k-2<\/sub>, v<sub>k-1<\/sub>}, {v<sub>k-1<\/sub>,v<sub>k<\/sub>}) von Kanten.<\/li>\n<li>Ein <strong>ordinary<\/strong> (gew\u00f6hnlicher) Path in einem <strong>gerichteten<\/strong> Graphen ist eine endliche, geordnete Sequenz ((v<sub>1<\/sub>,v<sub>2<\/sub>), (v<sub>2<\/sub>,v<sub>3<\/sub>), ..., (v<sub>k-2<\/sub>, v<sub>k-1<\/sub>), (v<sub>k-1<\/sub>,v<sub>k<\/sub>)) von Kanten.<\/li>\n<li>Ein <strong>generalized<\/strong> a.k.a. weak (genereller, schwacher) Path in einem <strong>gerichteten<\/strong> Graphen ist eine endliche Sequenz ((v<sub>1<\/sub>,w<sub>1<\/sub>), (v<sub>2<\/sub>,w<sub>2<\/sub>), ..., (v<sub>k-1<\/sub>, w<sub>k-1<\/sub>), (v<sub>k<\/sub>,w<sub>k<\/sub>)), so dass drehen von einigen Kanten einen ordinary Path ergibt (Ein ordinary Path ist schon ein generalized Path bei dem keine Kanten gedreht werden m\u00fcssen).<\/li>\n<li>Ein Path ist <strong>simple<\/strong> (einfach) wenn er keine Knoten doppelt enth\u00e4lt.<\/li>\n<li>Ein Knoten &#x1D461; &isin; &#x1D449 ist <strong>reachable<\/strong> (erreichbar) von &#x1D460; &isin; &#x1D449;, wenn es einen Path von  &#x1D460; nach &#x1D461; in dem Graph gibt.<br \/>\nAbh\u00e4ngig vom Kontext, der Path muss ein ungerichteter, ein gew\u00f6hnlicher gerichteter, oder ein generalized Path sein.<br \/>\nJeder Knoten ist von sich selbst aus erreichbar, via den trivialen Path welcher nur diesen Knoten enth\u00e4lt und sonst keine Kanten.<\/li>\n<li>Die <strong>internal<\/strong> (internen) Knoten von einem Path jeglicher Art sind alle Knoten von diesem Path au\u00dfer dem Start und Endknoten.<br \/>\n(Wenn der Start oder Endknoten mehr als einmal im Path vorkommt, z\u00e4hlt es zu den internen Knoten)<\/li>\n<li>Zwei Pathe sind <strong>edge-disjoint<\/strong> (disjunkt) wenn sie keine gemeinsame Kante haben. Sie sind <strong>(internally) node-disjoint<\/strong> wenn sie keine gemeinsamen Knoten haben.<\/li>\n<\/ol>\n<h2>Cycles<\/h2>\n<ol>\n<li>Ein (ordinaty\/gew\u00f6hnlicher) <strong>cycle<\/strong> in einem <strong>ungerichteten<\/strong> Graphen ist eine endliche, geordnete Sequenz ({v<sub>1<\/sub>,v<sub>2<\/sub>}, {v<sub>2<\/sub>,v<sub>3<\/sub>}, ..., {v<sub>k-2<\/sub>, v<sub>k-1<\/sub>}, {v<sub>k-1<\/sub>, <strong>v<sub>1<\/sub><\/strong>} ) von Kanten. In anderen Worten: Ein cycle ist ein Path, so dass der Startknoten gleich dem Endknoten ist.<\/li>\n<li>Ein (ordinaty\/gew\u00f6hnlicher) <strong>cycle<\/strong> in einem <strong>gerichteten<\/strong> Graphen ist eine endliche, geordnete Sequenz ((v<sub>1<\/sub>,v<sub>2<\/sub>), (v<sub>2<\/sub>,v<sub>3<\/sub>), ..., (v<sub>k-2<\/sub>, v<sub>k-1<\/sub>), (v<sub>k-1<\/sub>, <strong>v<sub>1<\/sub><\/strong>) ) von Kanten. In anderen Worten: Ein cycle ist ein Path, so dass der Startknoten gleich dem Endknoten ist.<\/li>\n<li>Ein <strong>generalized<\/strong> a.k.a. weak (genereller, schwacher) <strong>cycle<\/strong> in einem <strong>gerichteten<\/strong> Graphen ist eine endliche Sequenz ((v<sub>1<\/sub>,w<sub>1<\/sub>), (v<sub>2<\/sub>,w<sub>2<\/sub>), ..., (v<sub>k-1<\/sub>, w<sub>k-1<\/sub>), (v<sub>k<\/sub>,w<sub>k<\/sub>)), so dass drehen von einigen Kanten einen ordinary cycle ergibt (Ein ordinary cycle ist schon ein generalized cycle bei dem keine Kanten gedreht werden m\u00fcssen).<\/li>\n<li>A cycle is simple if no proper part is a cycle of its own. <\/li>\n<li>Ein gerichteter oder ungerichteter Graph ist <strong>acyclic (cycle-free)<\/strong>, wenn er kein ordinary cycle enth\u00e4lt. Ein gerichteten Graphen nennt man in diesem Fall <strong>DAG (directed acyclic graph)<\/strong>.<\/li>\n<li>F\u00fcr zwei Knoten &#x1D460;,&#x1D461; &isin; &#x1D449;, ein <strong>(s,t)-graph<\/strong> &#x1D43A; = (&#x1D449;, &#x1D434;) ist ein <strong>DAG<\/strong>, so dass &#x1D460; ist der einzige Knoten mit indegree 0, und &#x1D461; ist der einzige Knoten mit outdegree 0.<br \/>\nEin DAG ist ein <strong>(s,t)-Graph<\/strong> , genau dann, wenn der Graph G die Vereinigung von (nicht notwenigerweise internally Knoten oder Kanten disjunkt) allen (s,t)-pathen ist.<\/li>\n<\/ol>\n<h2>Forests, trees, branchings, arborescences<\/h2>\n<ol>\n<li>Ein <strong>forst<\/strong> ist ein <strong>cycle-free undirected<\/strong> Graph. <strong>Disconnected<\/strong> nicht vergessen sonst macht es kein Sinn.<br \/>\n<a href=\"http:\/\/roboblog.fatal-fury.de\/wp-content\/uploads\/2019\/05\/forest.png\" rel=\"attachment wp-att-4353\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/roboblog.fatal-fury.de\/wp-content\/uploads\/2019\/05\/forest.png\" alt=\"forest\" width=\"258\" height=\"214\" class=\"alignnone size-full wp-image-4353\" \/><\/a>\n<\/li>\n<li>Ein <strong>tree<\/strong> ist ein <strong>conected<\/strong> forst. Also connected, cycle-free undirected Graph.<br \/>\n<a href=\"http:\/\/roboblog.fatal-fury.de\/wp-content\/uploads\/2019\/05\/tree.png\" rel=\"attachment wp-att-4355\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/roboblog.fatal-fury.de\/wp-content\/uploads\/2019\/05\/tree.png\" alt=\"tree\" width=\"258\" height=\"214\" class=\"alignnone size-full wp-image-4355\" \/><\/a><br \/>\nDas ist nicht unbedingt das, was man von der Schule her noch kennt. In der Schule war ein tree immer ein directer Graph mit einem Wurzelknoten. Aber gut. Muss ja nicht.\n<\/li>\n<li>Ein <strong>branching<\/strong> ist ein cycle-free, directed Graph, so dass indregree f\u00fcr jeden Knoten 0 oder 1 ist. Das sieht gedanklich schon ehr wie ein Baum aus. Aber noch nicht ganz. Directed muss sein, klar. Sonst k\u00f6nnte man seine \"Entscheidungen\" beim \"branchen\" ja zur\u00fcck nehmen.<\/li>\n<li>Eine <strong>arborescene<\/strong> ist ein branching, so dass genau ein Knoten indegree 0 hat. Das nennt man auch <strong>rooted trees<\/strong> und der einzigartige Knoten mit indegree 0 ist <strong>root<\/strong>. DAS ist ein Baum.<\/li>\n<li>Ein forest\/tree\/branching\/arborescence in einem Graphen G ist ein Subgraph von G welcher wiederrum ein forest\/tree\/branching\/arborescence ist.<br \/>\nNaja, auf dem zweiten Blick stimmt das. Jeden Subgraph den man aus einem Tree rausholt ist wieder ein Tree.\n<\/li>\n<\/ol>\n<h2>Connectedness<\/h2>\n<p>Types of connectedness:<\/p>\n<ol>\nTypes of connectedness:<\/p>\n<li>Ein <strong>ungerichteter<\/strong> Graph ist <strong>connected<\/strong>, wenn jedes m\u00f6gliche Knotenpaar durch einen Path verbunden ist.<\/li>\n<li>Ein <strong>ungerichteter<\/strong> Graph ist <strong>k-connected<\/strong>, wenn jedes m\u00f6gliche Knotenpaar mindestens durch <strong>k internally node-disjoint Pathe<\/strong> verbunden ist. Einfach nur connected ist 1-connected. k=2 ist <strong>biconnected<\/strong>.<\/li>\n<li>Ein <strong>directed<\/strong> Graph ist <strong>weakly connected<\/strong>, wenn f\u00fcr jeden Knotenpaar ein <strong>generalized path<\/strong> existiert welcher diese Knoten verbindet.<\/li>\n<li>Ein <strong>directed<\/strong> Graph ist <strong>strongly connected<\/strong>, wenn f\u00fcr jedes <strong>geordnerte<\/strong> Knotenpaar ein <strong>ordinary path<\/strong> den ersten mit den zweiten Knoten verbindet.<\/li>\n<p>Links:<\/p>\n<li>Ein <strong>articulation<\/strong> Knoten in einem connected undirected Graph ist so ein Knoten, dass wenn der Knoten (und die angeschlossenen Kanten) entfernt wird, der Graph disconnected wird.<\/li>\n<li>Eine <strong>bridge<\/strong> in einem connected undirected Graph ist eine Kante, so dass der Graph disconnected wird wenn diese Kante entfernt wird.<\/li>\n<p>Connected components:<\/p>\n<li>Die <strong>k-connected componenten<\/strong> von einem ungerichteten Graphen  &#x1D43A; = (&#x1D449;, &#x1D438;) ist die <strong>inclusion-maximal Knotenmengen<\/strong> &#x1D449;' &sube; &#x1D449;, so dass der Subgraph von &#x1D43A;, hergestellt von &#x1D449;', <strong>k-connected<\/strong> ist (d.h. wenn jedes m\u00f6gliche Knotenpaar in V' mindestens durch k internally node-disjoint paths miteinander verbunden sind).<br \/>\nFor k=1 wir sagen connected und f\u00fcr k=2 wir sachen <strong>biconnected<\/strong> compoenten von G. <\/li>\n<li>Die <strong>weakly<\/strong> und <strong>strongly connecten componenten<\/strong> von einem directed Graph &#x1D43A; = (&#x1D449;, &#x1D434;) sind die <strong>inclusion-maximal Knotenmengen<\/strong> &#x1D449;' &sube; &#x1D449;, so dass der Subgraph von  &#x1D43A induced von &#x1D449;' ist weak und strong connected.<\/li>\n<\/ol>\n<h2>Bipartite and k-partite graphs<\/h2>\n<p>Sei &#x1D43A; = (&#x1D449;, &#x1D438;) ein ungerichteter Graph.<\/p>\n<ol>\n<li>Der Graph &#x1D43A; ist <strong>&#x1D458;-partite<\/strong>, wenn es eine <strong>&#x1D458;-partition<\/strong> {&#x1D449;<sub>1<\/sub>, ..., &#x1D449;<sub>k<\/sub>} von &#x1D449; gibt, so dass {&#x1D463;,&#x1D464;} &notin; &#x1D438; ist f\u00fcr jedes Paar &#x1D463;,&#x1D464; &isin; &#x1D449;<sub>i<\/sub> f\u00fcr jedes i &isin; {1,...,&#x1D458;}.<\/li>\n<li>F\u00fcr &#x1D458;=2 wir sagen &#x1D43A ist <strong>bipartite<\/strong>.<\/li>\n<\/ol>\n<p>Statement: Ein verbundener, ungerichteter Graph ist bipartite, genau dann wenn es kein Cycle von ungerade L\u00e4nge gibt.<br \/>\nDas l\u00e4sst sich leicht erkennen, wenn man die Knoten auf dem Path abwechseln  V1 und dann V2 zuordnet. Bei ungeraden L\u00e4ngen sind die Knoten der letzten Kante bei immer aus V1 oder V2.<\/p>\n<h2>Complete graphs<\/h2>\n<ol>\n<li>F\u00fcr eine positive ganzzahlige Nummer &#x1D45B;, der <strong>complet graph<\/strong> &#x1D43E;<sub>&#x1D45B;<\/sub> = (&#x1D449;,&#x1D438;) ist der einzigartige undirecte Graph, so dass |&#x1D449;| = &#x1D45B; und alle (ungeordneten) Paaren of Knoten in &#x1D438; sind. Das heisst jeder mit jedem. Dense.<\/li>\n<li>F\u00fcr positive ganzzahlige Nummern &#x1D45A; und &#x1D45B, der complete bipartite graph &#x1D43E;<sub>&#x1D45A;,&#x1D45B;<\/sub> = (&#x1D449;<sub>1<\/sub> UNITED &#x1D449;<sub>2<\/sub>, &#x1D438;) ist der einzigartige undirecte graph, so dass |&#x1D449;<sub>1<\/sub>| = &#x1D45A; und |&#x1D449;<sub>2<\/sub>| = &#x1D45B; und jeder (ungeordnete) Pair {&#x1D463;,&#x1D464;} mit &#x1D463; &isin; &#x1D449;<sub>1<\/sub> und &#x1D464; &isin; &#x1D449;<sub>2<\/sub> in &#x1D438; ist.<br \/>\nAlso jeder von dem einem mit jeder von dem anderen.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Shortcut links: Basic graph definitions (this page) Basics of shortest paths Gerichtete und ungerichtete Graphen Ein gerichteter Graph &#x1D43A; = (&#x1D449;, &#x1D434;) besteht aus einer endlichen Menge &#x1D449; von Knoten und einem multiset &#x1D434; von geordneten Paaren von Knoten. Die Elemente von &#x1D434; sind die gerichteten Kanten von &#x1D43A;. Ein ungerichteter Graph &#x1D43A; = (&#x1D449;, [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-4295","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4295","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4295"}],"version-history":[{"count":59,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4295\/revisions"}],"predecessor-version":[{"id":4382,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4295\/revisions\/4382"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4295"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4295"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4295"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}