Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Durchmesser Graphen nach einfügen Kante

Durchmesser Graphen nach einfügen Kante

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

NeueFrage12 aktiv_icon

20:41 Uhr, 06.03.2023

Hey, einmal die Aufgabe :
Sei

P = (V, E)

ein Pfad der Länge D. Wir fügen nun eine neue Kante zwischen zwei Konten von

V

hinzu. Zeigen Sie, dass der Graph, den wir erhalten, einen Durchmesser von mindestens

\frac{D}{2}

hat.

Meine Gedanken waren bis jetzt: Der Durchmesser ist ja als maximaler Abstand von zwei beliebigen Knoten definiert. Da es darum geht die Kante an beliebigen Knoten einzufügen und wir dann jedoch wissen wollen was dieser mindestens sein muss, hatte ich gedacht ,wird die Kante zwischen dem anfangs und Endknoten des Pfades eingefügt. Damit halbiert sich der maximale Abstand dieser beiden Knoten. Da wir nun, um den größten abstand zu bekommen , gegenüberliegende Knoten nehmen müssen (wir haben jetzt ja einen Kreis) . Hoffe es war einigermaßen verständlich was ich mir gedacht hatte. Habe noch ein Bild angefügt.Entschuldigt die Unschärfe.
Ist echt schwer auf dem Bild die Farben auseinander zu halten. Habe mit schwarz den Durchmesser vor dem Einfügen der Kante gekennzeichnet.
Der Abstand zweier Knoten (dist(u,v) ) ist bei uns als kürzester Pfad zwischen diesen definiert.

Macht meine Idee Sinn oder ist es Humbug ?

*EDIT : ich kann leider keine Bilder , warum auch immer, anfügen.

Gruß

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

michaL aktiv_icon

21:29 Uhr, 06.03.2023

Hallo,

Formalisierung hilft.

Letztlich hast du (der Einfachheit halber) die Ecken 1, 2, ...,

D

mit den Kanten

{x, x + 1}

für

x \in {1, 2, \dots, D - 1}

.

Nun fügst du eine Kante

{x, y}

hinzu. Das führt zu einem Kreis mit keinem, einem oder maximal 2 "Fortsätzen".

Interessant ist dabei, wie groß der Kreis ist und wie lang die "Fortsätze" als Pfade sind.
Da kann man aber - je nach Anzahl der Fortsätze - die Durchmesser relativ einfach bestimmen und einfach nachrechnen.

> *EDIT : ich kann leider keine Bilder , warum auch immer, anfügen.
Deren Größe darf 500 kB nicht überschreiten.

Mfg Michael

NeueFrage12 aktiv_icon

22:30 Uhr, 06.03.2023

Danke für die Antwort. Was genau meinst du mit Fortsätzen ?
Ist damit gemeint, wenn man als Knoten nicht die Endknoten nimmt und man so mit einen Kreis hat und weitere Kanten, die nicht zum Kreis gehören?
Heißt bei keinem Fortsatz wäre es ja wie ich oben geschrieben hatte, dann einfach

\frac{D}{2},

weil wir genau die hälfte „laufen“.
Aber wies dann mit Fortsätzen aussieht ,kann ich mir gerade irgendwie nicht vorstellen.
Ahh, ok. macht Sinn. Mein Bild hatte 2 MB.

Gruß

HAL9000

08:34 Uhr, 07.03.2023

@michaL

Länge

D

bedeutet doch

D

Kanten und damit aber

D + 1

Knoten

1, 2, \dots, D + 1

, oder sehe ich das falsch?

P.S.: Da ich nicht so vertraut bin mit der Terminologie der Graphentheorie: Die Formulierung, dass ein Graph ein Pfad "ist" soll wohl einfach bedeuten, dass der Graph nur aus diesem Pfad besteht, d.h. keine weiteren Kanten besitzt?

NeueFrage12 aktiv_icon

09:36 Uhr, 07.03.2023

Ja, genau so hatten wir es auch definiert.

michaL aktiv_icon

10:33 Uhr, 07.03.2023

Hallo,

äh, doch.
Vielleicht sollte ich mir doch angewöhnen, mein Geschreibsel nochmal zu revidieren. :/

Mit Fortsätzen meine ich, dass ja ein Kreis geschlossen wird. Der Graph sieht also wie ein Kreis (Vieleck) aus, von dem bis zu 2 Pfade wegführen.

Wen ich nachher Zeit habe, füge ich mal ein Bild ein.

Mfg Michael

NeueFrage12 aktiv_icon

12:19 Uhr, 07.03.2023

Ah, ne ist nicht Notwendig, ich habs nun verstanden was du meinst. Aber trotzdem danke. Ich verstehe noch nicht ganz wie man dann auf den Durchmesser mit Fortsätze kommt, da diese ja immer unterschiedlich lang sind, je nachdem wo die Kante eingefügt wird. Also genau genommen ist es ja dann, wenn man Knoten hat

v_{1} - v_{D} + 1

(der Pfad bildet Kanten mit

(v_{i}) + (v_{i} + 1))

und eine Kante

v_{k} + v_{j}

mit

k \neq j

und

j, k

im Wertebereich von

i

liegt , einfügt , der Durchmesser dist(v1,v_D+1) sich mit den Kanten

V_{1} + v_{2}, . ., v_{k} + v_{j}

,…,v_D-1

+ v_{D}

berechnet . So hätte man ja dann 2 Fortsätze. Wie kommt man dann hier auf

\frac{D}{2}

für den Durchmesser?

HAL9000

12:34 Uhr, 07.03.2023

Tatsächlich muss man den Durchmesser des Graphen gar nicht exakt bestimmen. Es reicht bereits aus, ein Knotenpaar mit einer Entfernung

\frac{D}{2}

zu finden.

Z.B.: Als einen Knoten nimmt man den Endknoten des längeren der beiden Fortsätze, und als anderen den Knoten im Kreis, der am weitesten davon entfernt ist.

michaL aktiv_icon

12:44 Uhr, 07.03.2023

Hallo,

es geht ja nur darum, zwei Ecken anzugeben, deren Abstand mindestens

\frac{D}{2}

beträgt.

Ich denke mir also die Knoten

1

2

, ...,

D + 1

, die der Reihe nach durch Kanten

{x, x + 1}

(

x \in {1, \dots, D}

) verbunden sind.

Nun werden die Elemente

k

und

l

mit

0 \leq k < l - 1 \leq D

durch eine direkte Kante verbunden.
(Ich nehme jedenfalls mal an, dass nicht

l = k + 1

gelten darf, da es diese Kante schon gibt.)
Damit liegen einerseits der Pfad

1 2 \dots k

und andererseits

l l + 1 \dots D + 1

außerhalb des Kreises

k k + 1 \dots l k

.

Der Durchmesser dieses Kreises wird bestimmt durch

⌈ \frac{l - k + 1}{2} ⌉

, d.h. es gibt Elemente im Kreis, die genau diesen Abstand von den Knoten

k

oder

l

haben.
Am dichtesten dran am Kreis sind die Enden der "Fortsätze" (wenn es denn zwei sind) dann, wenn auf beiden Seiten gleich viele Elemente sind. Das sind dann

⌈ \frac{D + 1 - (l - k + 1)}{2} ⌉ = ⌈ \frac{D + k - l}{2} ⌉

.

Wie ich eben bei HAL9000 lese, sieht er es genauso.
Die beiden Abstände sind zu addieren.
Wenn du willst, kannst du da eine Fallunterscheidung machen. Der kleinste Wert ergibt sich, wenn beide Brüche selbst schon ganz sind.

Mfg Michael

HAL9000

12:54 Uhr, 07.03.2023

Ich hab mich in meinem letzten Beitrag verschrieben: Statt

\frac{D}{2}

war dort natürlich

\geq \frac{D}{2}

gemeint, aber habt ihr euch wohl schon gedacht. ;-)

NeueFrage12 aktiv_icon

13:02 Uhr, 07.03.2023

Ah, jetzt hab ich es verstanden. Danke schonmal. Ich hab noch eine Frage zum Durchmesser des Kreises . Warum muss man noch 1 addieren?
Nach einer Skizze und Beispielen ist es mit klar geworden, aber eine formale Begründung konnte ich mir nicht erklären. Liegt es daran, dass durch das einfügen ja eine Kante mehr dazukommt und deshalb der Abstand von

k

und

l +

(eine zusätzliche Kante)

/ 2

genommen werden muss?
Gruß

NeueFrage12 aktiv_icon

13:02 Uhr, 07.03.2023

k

und

l +

(eine zusätzliche Kante)

/ 2

genommen werden muss?
Gruß

michaL aktiv_icon

13:27 Uhr, 07.03.2023

Hallo,

offenbar hast du einen nervösen Zeigefinger.
Das Absenden dauert nun mal ein bisschen. Sende es nicht vorschnell doppelt.

> Ich hab noch eine Frage zum Durchmesser des Kreises . Warum muss man noch 1 addieren?

Hm, wenn du dir mal eine Zeichnung/Skizze machtest, dann wüsstest du, warum.

Nehmen wir doch mal für

k = 2

und für

l = 5

. Es sind also die Ecken 2, 3, 4 und 5 im "Kreis".

Das sind 4 Ecken. also einer mehr als

l - k = 5 - 2

.

Das Problem bei solchen Sachen ist, dass durch die Subtraktion von

k

dieser Knoten als NICHT dazugehörig gewertet wird.
Der letzte, nicht zugehörige Knoten ist aber

k - 1

.
Ergo muss man

l - (k - 1)

rechnen, was aber eben

l - k + 1

ergibt.

Gleiches tritt bei Tagen auf. Die Anzahl der Tage, die zwischen dem 5. (einschließlich) und dem 2. (auch eingeschlossen) liegt, ist nicht

5 - 2 = 3

.

Mfg Michael

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1568161

1568102

	Status: nicht eingeloggt	Noch nicht registriert?