 |
 |
 |
 |
 |
 |
Startseite » Forum » Überdeckung eines Graphen
Überdeckung eines Graphen
Universität / Fachhochschule
Graphentheorie
Tags: Graphentheorie
 
|
  |
|---|
|
Ich habe mir mal folgende Frage gestellt: Gegeben sei ein (einfacher) Graph . Ich definiere mir den Ball Jetzt sei ein gegeben. Wie viele Bälle mit Radius brauche ich, um den Graphen vollständig zu überdecken, also sodass die Vereinigung aller Bälle jeden Knoten von enthalten. Mir ist bewusst, dass diese Frage nicht leicht zu beantworten ist. Vielleicht kennt jemand von euch Paper die sich damit befassen, oder vielleicht hat jemand von euch interessante Vorgehensweisen um das Problem zu lösen... |
|
 |
|
Hallo, kann es sein, dass die Definition von so lauten sollte: ? Und dann stellt sich die Frage, wie der Abstand definiert ist. Anzahl der minimal zurückzulegenden Kanten? Die Antwort ist für einfach, da gilt. (Unter der Voraussetzung, dass ich den Abstand korrekt verstanden habe.) Überlege doch einfach mal, wie das für ist. Mfg Michael |
 |
|
Ja stimmt, da hatte ich einen kleinen Denkfehler. Die Abstandsfunktion soll auch genau so sein wie du sie verstanden hast :-) Ok für benötigt man natürlich Bälle, da wie du schon gesagt hast . Für ist das schon interessanter, ich glaube, dass folgende Abschätzung gilt: Anzahl der Bälle Eine Gleichheit kann man sicherlich nicht finden, da . eine Linie mit 5 Knoten 2 Bälle vom Radius 1 und der vollständige Graph nur ein Ball vom Radius braucht. Soweit erstmal richtig? Gehen nich bessere Abschätzungen? Vielen Dank erstmal |
|
|
|
Hallo, korrekt. Ich denke, es kann nur darum gehen, Abschätzungen zu finden. Dass die Anzahl der Bälle vom Radius , die man zur Überdeckung benötigt, mindestens ist, zeigt man dadurch, dass man einen Graphen findet, bei dem weniger Bälle nicht ausreichen. Dass die Zahl aber immer ausreicht, muss auch gezeigt werden. Ich würde mich mal durch einige Werte von durchkämpfen. Ist über den Graphen was bekannt? Problematisch sind halt die vollständig isolierten Graphen, also diejnigen, bei denen der Komplementärgraph vollständig ist. Mfg Michael |
|
|
|
Ja. Ich frage mich, was du mit meinst.... Aber stimmt, wenn ich zeigen will das mindestens Bälle ausreichen um den Graphen zu überdecken muss ich zeigen, dass eine Überdeckung mit weniger nicht möglich ist. Aber was ich nicht ganz verstehe: Warum muss ich auch zeigen, dass die Zahl auch immer ausreicht, wenn ich doch aber von mindestens spreche? Mindestens heißt doch, es geht nicht mit weniger, aber es muss auch nicht unbedingt mit genau funktionieren. Über die Graphen ist leider nichts bekannt, ich habe mir die Frage schließlich selber ausgedacht, für mögliche Abschlussarbeiten... Also das ist wirklich nicht ganz einfach sich für die verschiedenen durchzukämpfen :-) Was meinst du welche Graphen könnte man zuerst untersuchen? Bäume vielleicht oder so ?? |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1267126
1266581