Forum:  Graphentheorie
Thema: Stark zusammenhängend?
Themen-Übersicht
hellomath
Junior
Dabei seit: 07.05.2020
Mitteilungen: 18
Aus:
Themenstart: 2020-06-03 20:21

Hallo! Ich habe folgenden Graphen:





Er ist lexikographisch geordnet, das heißt also nicht stark zusammenhängend, da z.B. a von b aus nicht erreichbar ist, wenn ich das richtig verstanden habe?


In der Angabe ist folgendes gegeben:

Falls G nicht stark zusammenhängend ist, geben Sie eine minimale Kantenmenge an mit welcher G stark zusammenhängend wird.



Ich verstehe leider nicht ganz, was jetzt zu tun ist? Wäre sehr dankbar für eure Hilfe!



Gruß


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6051
Aus: Milchstraße
Beitrag No.1, eingetragen 2020-06-03 20:48

Hallo hellomath,

wenn ich die Aufgabe richtig verstehe, verlaufen in deinem Graphen alle Kanten von links nach rechts bzw. von oben nach unten.

Nun sollen einige Kanten hinzugefügt werden, sodass man von jeder Ecke jede andere Ecke erreichen kann.

Z. B. kann die Kante (d, e) hinzufügen. Dann kommt man schon mal von d nach e, f, g, i, j und k - was vorher nicht ging.

Aber von f nach e geht es immer noch nicht.

Es sollen so wenig Kanten wie möglich hinzugefügt werden.



hellomath
Junior
Dabei seit: 07.05.2020
Mitteilungen: 18
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2020-06-03 22:05

Hi! Vielen vielen Dank!

Also eigentlich müsste man nur bei d eine Kante hinzufügen die zu e führt und eine bei h eine Kante die zu i führt, sehe ich das richtig?

Oder, angenommen man darf vorhandene Kanten entfernen, entfernt man alle Kanten die "nach unten" zeigen, behält die waagrechten verbindungen und fügt aber d->e und h-> i hinzu


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6051
Aus: Milchstraße
Beitrag No.3, eingetragen 2020-06-03 22:32

2020-06-03 22:05 - hellomath in Beitrag No. 2 schreibt:
Also eigentlich müsste man nur bei d eine Kante hinzufügen die zu e führt und eine bei h eine Kante die zu i führt, sehe ich das richtig?

Dann kommt man aber immer noch nicht von f nach e.

Kanten zu entfernen ist hier m. E. nicht verlangt.


hellomath
Junior
Dabei seit: 07.05.2020
Mitteilungen: 18
Aus:
Beitrag No.4, vom Themenstarter, eingetragen 2020-06-04 15:41

Ich dachte, da es lexicographisch geordnet ist, muss diese Bedingung nicht erfüllt sein, da f nach e im Alphabet vorkommt?

Oder habe ich das falsch verstanden?


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6051
Aus: Milchstraße
Beitrag No.5, eingetragen 2020-06-04 16:36

Mir ist noch nicht ganz klar, wie der Graph definiert ist. Soll gelten

\(E=\{(\xi,\eta)\in\{a,b,...,\ell\}^2:\xi\text{ kommt im lateinischen Alphabet vor }\eta\}\)

Oder geht es potentiell nur um die Kanten, die in deiner Zeichnung vorkommen?

Wie auch immer. (f, e) ist keine Kante. Du könntest die Kante aber hinzufügen. Dann kommt man von f nach e. Du musst Kanten so hinzufügen, dass man im erweiterten Graph von jeder Ecke zu jeder anderen Ecke gelangen kann. Der erweiterte Graph ist dann nicht mehr lexikographisch geordnet.


hellomath
Junior
Dabei seit: 07.05.2020
Mitteilungen: 18
Aus:
Beitrag No.6, vom Themenstarter, eingetragen 2020-06-04 17:29

Die Definition habe ich hingeschrieben, genauer wurde er nicht definiert :)

Wenn es nicht mehr lexikographisch sein muss, könnte ich doch l mit a verbinden und somit mit nur einer Kante mehr den Graphen stark zusammenhängend machen, stimmt das?


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6051
Aus: Milchstraße
Beitrag No.7, eingetragen 2020-06-04 18:45

2020-06-04 17:29 - hellomath in Beitrag No. 6 schreibt:
Wenn es nicht mehr lexikographisch sein muss, könnte ich doch l mit a verbinden und somit mit nur einer Kante mehr den Graphen stark zusammenhängend machen, stimmt das?

Das ist des Pudels Kern! 👍


hellomath
Junior
Dabei seit: 07.05.2020
Mitteilungen: 18
Aus:
Beitrag No.8, vom Themenstarter, eingetragen 2020-06-04 19:41

Super! Vielen Dank!




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=247860=7080
Druckdatum: 2020-08-10 10:51