Unabhängigkeitszahl von Graphen |
| 17.03.2004, 18:02 | Krautzi04 | Auf diesen Beitrag antworten » |
| Unabhängigkeitszahl von Graphen Soll ja anscheinend für jeden Graphentyp eine allgemeine Formel sein. Mit kleinen Knotenzahlen man das ja durchprobieren aber ich finde keine allgemein gültige Fomel. Die Unabhängigkeit ergibt sich aus der Anzahl der Knoten, die nicht miteinander verbunden sind. Hat jemand einen Ansatz ? Thanx. Krautzi |
||
| 17.03.2004, 22:20 | Ben Sisko | Auf diesen Beitrag antworten » |
| RE: Unabhängigkeitszahl von Graphen Verstehe ich das richtig, dass die Unabhängigkeitszahl die Anzahl der Zusammenhangskomponenten angibt? Und was verstehst du unter den angegebenen Bezeichnungen? Kreis=Graph, der nur aus einem Kreis besteht? Dann wäre das 1. Pfad=Graph, der nur aus einem Pfad besteht? Ebenfalls 1. bipartiter Graph? 2. Allgemeiner Graph? Keine Ahnung. So kann das aber eigentlich nicht richtig sein. Bitte erklär nochmal genauer, was du unter Unabhängigkeit verstehst. Gruß vom Ben |
||
| 17.03.2004, 22:45 | Krautzi04 | Auf diesen Beitrag antworten » |
Ein Kreis als Graph besteht aus Knoten die durch Kanten miteinander verbunden sind. (ich habs versucht hier hin zu 'zeichnen' aber es wird nicht richtig formatiert.) Ein Kreis besteht zB aus 6 Knoten.Nur die oberen und die unteren Knoten sind dann direkt durch je eine Kante verbunden. Die beiden 'mittleren' haben keine Kante die sie direkt verbindet (dann wäre es praktisch ein Kreis mit 'Strich' in der Mitte) Diese zwei Knoten nennt man 'unabhängig'. Ich brauche eine Formel mit der man die Unabhängigkeitszahl berechnen kann, wenn es 6 und mehr Knoten gibt. C(1) geht nicht, mindestens 3 Knoten, um einen Kreis zu bilden. C(6) = 2 C(3) = ? Das ganze ist Diskrete Mathematik im Informatikstudium. Ich habe das auch schon in einem anderen Forum gepostet. Das ganze ist vielleicht etwas zu speziell für das Forum hier, ich dachte ich versuchs mal. |
||
| 17.03.2004, 23:27 | epikur | Auf diesen Beitrag antworten » |
Im K_n ist jeder Knoten mit jedem Verbunden, also ist die Unabhängigkeitszahl 1. Im C_n kann man immer jeden zweiten Knoten in die unabhängige Menge nehmen, damit kommt man auf eine Mächtigkeit von floor(n/2) und man kann sich leicht überlegen das dieser Wert maximal ist. Mit bipartitem Graphen nehme ich an du meinst den vollständigen bipatiten Graphen B_(n,m), hier ergibt sich die Unabhängigkeitszahl als max(m,n) und für einen Pfad P_n als ceil(n/2). Für beliebige bipartite Graphen kann man keine allgemeine Formel angeben. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
