Matroids Matheplanet Forum Index
Moderiert von matroid
Kombinatorik & Graphentheorie » Graphentheorie » Stark zusammenhängend?
Druckversion
Druckversion
Autor
Universität/Hochschule J Stark zusammenhängend?
hellomath
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 07.05.2020
Mitteilungen: 18
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-06-03


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ß



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6051
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-06-03


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.




Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hellomath
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 07.05.2020
Mitteilungen: 18
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2020-06-03


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



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6051
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-06-03


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hellomath
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 07.05.2020
Mitteilungen: 18
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, vom Themenstarter, eingetragen 2020-06-04


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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6051
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-06-04


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.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hellomath
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 07.05.2020
Mitteilungen: 18
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-06-04


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?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6051
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-06-04


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! 👍



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hellomath
Junior Letzter Besuch: im letzten Quartal
Dabei seit: 07.05.2020
Mitteilungen: 18
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, vom Themenstarter, eingetragen 2020-06-04


Super! Vielen Dank!



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
hellomath hat die Antworten auf ihre/seine Frage gesehen.
hellomath hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]