Graphentheorie: Gallai Tree

23.07.2007, 11:05

Mattim

Graphentheorie: Gallai Tree

Moin moin,

hab mal wieder ein Definitionsproblem:

Gallai tree:
"A block of a graph G is its maximal 2-connected subgraph. A connected graph G is said to be a gallai tree if each of the blocks of G is a complete graph or an odd cycle."

das hört sich so an als gäbe es nur einen block. nämlich den größten 2 zusammenhängenden teilgraphen. aber dann heißt es auf einmal JEDER block von G... verwirrt

und:
Theorem: Let G be a connected graph with a list assignment L such that |L(v)| $\begin{eqnarray*} \geq \end{eqnarray*}$ deg(v) for each vertev v of G and G ist not L-colourable.
Then |L(v)| = deg(v) for every v and G is a Gallai tree. Moreover if G is 2-connected, the the lists L(v) of all the vertices v of G are the same.

Gibt das Sinn? Wenn die Anzahl der Listeneinträge größer/gleich des Eckengrades ist und G mit diesen Listen nicht färbbar ist, dann ist auf einmal |L(v)| = deg(v)?

Hoffe ihr könnt mir helfen. Dieses Theorem brauche ich für jeden kommenden Satz... Danke schonmal

Gruß
Matti

24.07.2007, 21:05

Abakus

Auf diesen Beitrag antworten »

RE: Graphentheorie: Gallai Tree

Zitat:

Original von Mattim
hab mal wieder ein Definitionsproblem:

Gallai tree:
"A block of a graph G is its maximal 2-connected subgraph. A connected graph G is said to be a gallai tree if each of the blocks of G is a complete graph or an odd cycle."

das hört sich so an als gäbe es nur einen block. nämlich den größten 2 zusammenhängenden teilgraphen. aber dann heißt es auf einmal JEDER block von G... verwirrt

Ja, liest sich für mich auch merkwürdig. Kannst du die Bedeutung aus dem Zusammenhang erarbeiten ? Was bedeuten die vorkommenden Begriffe (zB max. 2-connected subgraph) ?

Ich habe folgendes gefunden:

Zitat:

"A maximal by inclusion connected subgraph B of a graph G such that every two edges of B are contained in a cycle of G is called a block of G."

Vielleicht hilft das ja schon weiter.

Grüße Abakus smile

25.07.2007, 13:36

Mattim

Auf diesen Beitrag antworten »

Hi,
danke. 2 connected ist wohl das gleich wie 2-zusammenhängend. da passt deine definition rein. also es gibt zwischen 2 ecken 2 disjunkte wege.

ist ein block dann der 2 zusammenhängende teilgraph der die meisten ecken hat? oder worauf bezieht sich das maximal?

und wie dass dann in das folgende theorem zur listenfärbung reinpasst versteh ich gar nicht verwirrt

immer diese englische vieldeutigkeit...

danke nochmal

matti

25.07.2007, 14:15

Tomtomtomtom

Auf diesen Beitrag antworten »

Aus Bollobas "Modern Graph Theory" (leicht gekürzt):

Zitat:

Having seen how useful it is to partition a graph into its components (e.g. maximal connected subgraphs), letus attempt a similar decomposition using all maximal 2-connected subgraphs.

(früher definiert: eine Kante ist eine Brücke, wenn ihr entfernen die Anzahl der Komponenten erhöht)

A subgraph B of a graph G is a block of G if either it is a bridge or else it isa maximal 2-connected subgraph of G.

Two blocks have at most one vertex in common.

If x,y are distinct vertices of a block B, then G-edges(B) contains no x-y-path.

Recalling that a cycle is 2-connected and an edge is a bridge if and only if no cycle contains it, we find G decomposed into its blocks B_1, B_2, ... in the following sense: $\begin{eqnarray*} E(G)= \sum E(B_i), E(B_i) \cap E(B_j) = \emptyset if i \neq j \end{eqnarray*}$

Das maximal bezieht sich darauf, daß du alle 2-zusammenhängenden Graphen nimmst, die du nicht mehr durch hinzunahme weiterer Ecken/Kanten erweitern kannst, so daß sie 2-zusammenhängend bleiben. Jeder solche Teilgraph ist ein Block. Bei dejn restlichen Fragen kenn ich mich nicht aus.

25.07.2007, 23:26

Abakus

Auf diesen Beitrag antworten »

Maximal bedeutet hier inklusionsmaximal, d.h. du kannst zu einem Block keine weitere Kante dazunehmen, ohne die Eigenschaft 2-Zusammenhang kaputt zu machen.

Das Theorem solltest du dir erstmal an Beispielen klarmachen. Entscheidend ist hier wohl, was genau eine L-assignment ist. Das Theorem ist bestimmt auch bewiesen, d.h. du kannst auch in den Beweis reinschauen.

Grüße Abakus smile

26.07.2007, 09:31

Mattim

Auf diesen Beitrag antworten »

na, das gibt sinn! super vielen dank. das hilft mir weiter. dann werd ich mich nochmal an das theorem dransetzen (wird leider nicht bewiesen).
L-assignment hab ich mir mal frei übersetzt. Also L-assignment als eine Zuweisung der Listen L(v) zu den Ecken von G. Hoffe das kommt hin.

Danke Danke
Gruß
Matti

26.07.2007, 12:20

Mattim

Auf diesen Beitrag antworten »

wäre das: http://www.somazone.de/gallaitree.pdf also ein gallai tree?
die blocks sind dann entweder complete, völlständig, oder ungerade kreise.

Neue Frage »

Antworten »

Graphentheorie: Gallai Tree

Verwandte Themen