Hallo,
du kannst es zumindest informal beantworten, wenn du dir ein paar Dinge überlegst.
1. Ist dir klar was Zusammenhangskomponenten sind? Der Begriff ist eigentlich ziemlich intuitiv.
2. Ich gehe davon, dass deine Graphen einfach und ungerichtet sind, also keine Pfeile, sondern nur Kanten und es darf keine doppelten Kanten zwischen zwei Knoten geben. Sonst musst du es dir für deine Graphen überlegen.
3. Wenn du \(6\) Knoten hast, dann kannst du wie viele Kanten maximal haben? Stichworte: vollständiger Graph & \(\binom{n}{2}\).
4. Kennst du die Idee des minimalen Spannbaums?
Wenn du gar keine Ahnung hast, kannst du meine Lösung markieren! :)
Lösung:
1.Punkt: Ein Graph mit \(6\) Knoten kann höchstens \(15\) Kanten haben. Wenn er \(15\) Kanten hat, ist er vollständig. Vollständige Graphen bestehen selbstverständlich nur aus einer einzigen Zusammenhangskomponente.
2.Punkt: Wenn du \(6\) Knoten hast und immer von einem Knoten zu einem neuen läufst, musst du \(5\) Kanten einzeichnen und hast die gesamten Knoten des Graphs abgedeckt. Somit muss \(G\) aus mindestens \(5\) Kanten bestehen. Du kannst dir außerdem überlegen, dass du es mit \(5\) Kanten aber auch schaffen kannst zwei oder sogar drei Zusammenhangskomponenten zu haben, indem du entweder zwei Knoten komplett weglässt, oder einmal \(3\) Knoten mit \(3\) Kanten bzw. \(3\) Knoten mit \(2\) Kanten verbindest! :)
Student, Punkte: 2.6K