Antworte auf:  Stark zusammenhängend? von hellomath
Forum:  Graphentheorie, moderiert von: matroid

[Zur Forum-Gliederung] [Wie man Fragen beantwortet] [Themenstart einblenden]

  Alle registrierten Mitglieder können Mitteilungen schreiben.
Benutzername:
Passwort:
Nachricht-Icon:                   
                  
              
Nachricht:


 

Erledigt J


Input assistance tools (JavaScript): [Link extern intern] [MathML?] [$$?]
[fed-area] [LaTeX-inline] [LaTeX-display] [Tikz] [hide-area][show-area] [Source code [num.]][?]
 Show Preview      Write using fedgeo formula editor or Latex.

Smilies for your message:
😃 😄 😁 🙂 🙃 😉 🤗 🤫 🤔 🙄 😴 🤒 😎 😮 😲 😂
🙁 😖 😒 😐 😡 👌 👍 👎 🤢 🤧 🥵 🥶 😵 🤯 😛 😷
Optionen: Deaktiviere HTML in dieser Nachricht
Deaktiviere MATHML in dieser Nachricht. Wenn Dein Text $-Zeichen enthält, die nicht LaTeX-Formeln begrenzen.
Deaktiviere Smilies in dieser Nachricht
Zeige die Signatur (Kann in 'Mein Profil' editiert werden.)
    [Abbrechen]
 
Beachte bitte die [Forumregeln]


Themenübersicht
hellomath
Junior
Dabei seit: 07.05.2020
Mitteilungen: 18
Herkunft:
 Beitrag No.8, eingetragen 2020-06-04 19:41    [Diesen Beitrag zitieren]

Super! Vielen Dank!


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 6060
Herkunft: Milchstraße
 Beitrag No.7, eingetragen 2020-06-04 18:45    [Diesen Beitrag zitieren]

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
Herkunft:
 Beitrag No.6, eingetragen 2020-06-04 17:29    [Diesen Beitrag zitieren]

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: 6060
Herkunft: Milchstraße
 Beitrag No.5, eingetragen 2020-06-04 16:36    [Diesen Beitrag zitieren]

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
Herkunft:
 Beitrag No.4, eingetragen 2020-06-04 15:41    [Diesen Beitrag zitieren]

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: 6060
Herkunft: Milchstraße
 Beitrag No.3, eingetragen 2020-06-03 22:32    [Diesen Beitrag zitieren]

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
Herkunft:
 Beitrag No.2, eingetragen 2020-06-03 22:05    [Diesen Beitrag zitieren]

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: 6060
Herkunft: Milchstraße
 Beitrag No.1, eingetragen 2020-06-03 20:48    [Diesen Beitrag zitieren]

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
Herkunft:
 Themenstart: 2020-06-03 20:21    [Diesen Beitrag zitieren]

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ß


 
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]