Do 8. Mai 11:10:43 CEST 2025 - graphauswendig20250505 txt

 
(C) David Vajda as Excerpt ...
siehe Algo Math, Fernuni Hagen
2025-05-05

Graph

G = (V,E)

V = {1,2,3,4}
E = {{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}

G = (V,E)
G = {{1,2,3,4},{{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}}}

Vollstaendige Graph K_n
Kreis C_n
Weg P_n

Vollstaendige Graph: zwischen allen knoten (v,w) in V besteht ein weg
zusammenhaengender Graph, ...

Kreis
V = {1,...,n}
E = {{i,i+1},...}, fuer i = {1,...n}, {n,1}

Weg
V = {1,...,n}
E = {i,i+1}, fuer i = {1,...,n}

Weg, Isomorphismus

(e1,v2,e2,v2,...,e_n,v_{n+1}): weg definiert als menge von 2n+1-tupel und kanten
(e1,e2,...,en): weg definiert als sequenz von kanten
(v1,v2,...,vn): weg definiert als sequenz von knoten

weg: weg ist ein isomorphismus eines pfades P_n zwischen knoten (v,n)

DFS - depth first search - tiefensuche
BFS - breath first search - breitensuchea

auf gut deutsch

ich nehme den ersten knoten und tue ihn in die schlange
vorne:
    ich nehme einen knoten von der schlnage
        suche alle nachbarn
        tue jeden nachbarn auf die schlange
    wenn ich mit den nachbarn durch bin
dann beginne ich von vorne

tiefensuche

ich nehme den naechsten knoten
    ich suche alle nachbarn
        ich gehe in den nachbarn
            und suche alle nachbarn
                ...

                rekursion

adjazenzmatrix, adjazenzliste als darstellung

eulertour - logisch

knotenzusammenhaengend, kantenzusammenhaengend

ein graph aus komponenten oder sagen wir kreisen
2 zusammenhaengend: ich tue zwei raus, der graph ist nicht mehr zusammenhaengend
gut: kantenzusammenhaengend, knotenzusammenhaengend

beispiel kreise gut gemacht

kreis: 2 zusammenhang

zusammenhangszahl, knoten o. kanten: bedeutet: so und so viel knoten oder kanten

kreis: 2 kanten raus, nicht zwei knoten, bedeutet 4 knoten
nicht mehr zusammenhaengend

wenn an einer stelle knoten raus, ganz als pfad.

ohrenzerleung
    C_n, kreis mit ausgezeichneten knoten (v,w) in C_n
    C_n = G\{E_x}
    v != w und v_i und w_j  i < j-1 ... und umgekehrt. aber nicht gleich usw

    Partition:
        E_1, E_2, E_3, ...

    E_1 ist Pfad, mit Anfang w und Ende v
        ... E_2

Ohrenzerlegung ist seltsamerweise niemals 2 zusammenhangszahl kann gar nicht sein

ausser minimal

weil, auch nicht


Operationen
    einfuegen einer Kante E+e
    entfernen einer kante E\e
    entfernen eines Knotens V\v
    Verschmelzen
    unterteilen

MST - minimum spanning tree

tree: ist ein kreisfreier graph

regeln
    (V,E) ist ein Baum
    zwischen allen knoten v und w besteht ein pfad, zusammenhang
    ...
    |E| = |V| -1 kreisfrei ..
    |E| = |V| -1 zusammenhaengend


wurzelbaum, mit ausgezeichneten knoten r

ein baum mit zwei blaettern, hat mindesten eine kanten ...

T = (E,r)
T = (E,r,roh)

roh, heisst, dass wir eine permutition isomorphismus haben

konsekutiv
s...

roh(v)
und roh(v) != roh(w) fuer w != v

permutationn


wurzelbaum aboresez, mit wurzel
mst
usw.

halt, vergessen, distanz, zentrum, exzentritaet

dist_G(u,v) = minimale astad zwische u und klei v im graph
ex_G(u,v) ist die distaz zwischen u und v, von u ausgehen im baum

zentrum ist so zu sagen, vermutung, der knoten bei die summe aller ... pfade, die laange die summe am kuerzesten ist

kann das sein? vorsicht

induktionsbeweis nehme ich an:

ueberpruefung

a-b-c

a: abstand (b,1), (c,2)
b, (a,1), (c,1)
c: abstand (a,2), (b,1)

b, summe 2

vergessen code

blaetter (),() ...

bei isomorphie nr. unterbringen?