EA (Fach) / Graphen und Graphendarstellung (Lektion)

Diese Lektion wurde von balduin erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

• Welche Eigenschaften hat ein Graph? gerichtet/ungerichtet gewichtet/ungewichtet dünn/dicht stark/schwach/zweifach zusammenhängend Artikulationspunkte kritische punkte
• Was ist ein dünner Graph Ein dünner Graph ist ein Graph mit einem Kanten-zu-Knoten-Verhältnis |E| << |V|2
• Was ist ein dichter Graph? Ein dichter Graph ist ein Graph mit einem Kanten-zu-Knoten-Verhältnis |E| ≅ |V|2
• Was heißt stark zusammenhängend ->stark zusammenhängend: Zwei Knoten u und v in einem gerichteten Graphen G = (V, E) heißen stark zusammenhängend, genau dann wenn in G ein gerichteter Weg von u nach v und von v nach u existiert ->G heißt stark zusammenhängend, falls G von jedem Knoten v aus V zusammenhängend ist
• Was heißt schwach zusammenhängend? Ein gerichteter Graph heißt schwach zusammenhängend, falls der zugehörige ungerichtete Graph (jede gerichtete Kante durch ungerichtete ersetzen) zusammenhängend ist
• Was ist eine starke Zusammenhangskomponente? Ein induzierter Teilgraph G_0 von G heißt starke Zusammenhangskomponente, falls G_0 stark zusammenhängend ist und es keinen größeren Teilgraphen gibt, der G_0 enthält und stark zusammenhängend ist
• Was heißt zusammenhängend Ein ungerichteter Graph G heißt zusammenhängend, wenn es von jedem Knoten u zu jedem anderen Knoten v mindestens einen Weg gibt.
• Was heißt zweifach zusammenhängend? Ein ungerichteter Graph G = (V, E) heißt zweifach zusammenhängend (biconnected), wenn nach dem Entfernen eines beliebigen Knotens v aus G der verbleibenden Graph G-v zusammenhängend ist
• Was ist eine zweifache Zusammenhangskomponente? Eine zweifache Zusammenhangskomponente (biconnected component) eines ungerichteten Graphen ist ein maximaler, zweifach zusammenhängender Untergraph
• Was ist eine Zusammenhangskomponente? Ein maximaler zusammenhängender Teilgraph eines ungerichteten Graphen G heißt Zusammenhangskomponente von G.

zurück  |  weiter 1 / 1