Abschätzung anzahl Kanten < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
Ups habe gemerkt, dass meine Begriffe (Ecken und Knoten) nicht ganz sauber waren und die Beschreibung nochmal überarbeitet.
| Aufgabe | Sei k [mm] \in \IN [/mm] mit k > 1 und [mm] H_k(V) [/mm] die Menge der ungerichteten Hypergraphen über einer gegebenen Menge von Ecken V mit v=|V| (v [mm] \ge [/mm] k), mit folgender Definition:
[mm] H_k(V):= [/mm] { (V, E) | [mm] (\forall [/mm] e [mm] \in [/mm] E : e ist genau zu k verschiedenen Ecken in V inzident)
[mm] \wedge (\forall [/mm] (x,y) [mm] \in [/mm] V [mm] \times [/mm] V : [mm] \exists [/mm] e [mm] \in [/mm] E: e ist inzident zu x und y) }
d.h. für jedes mögliche Paar von Ecken (x,y) [mm] \in [/mm] V [mm] \times [/mm] V gibt es min. eine Kante, die zu beiden Ecken inzident ist.
Wenn nun f als Funktion definiert ist, die für jeden der Hypergraphen aus [mm] H_k(V) [/mm] die Anzahl der Kanten zurückliefert, also
f: [mm] H_k(V) \to \IN [/mm] h [mm] \to [/mm] Anzahl der Kanten in h
wie groß ist dann
min { f(h) | h [mm] \in H_k(V) [/mm] }
unter Berücksichtigung von |V| und k? |
Das ist keine Aufgabe, die irgendwo in einem Lehrbuch stand, oder als Übungsaufgabe angegeben war, sondern eine Frage, für die ich selbst eine Antwort suche.
Gibt es hier bereits eine exakte Lösung, bzw eine Abschätzung?
Falls es keine exakte Lösung gibt, würde mich vor allem die untere Abschätzung interessieren.
Es gab wohl übrigens mal eine ähnliche Aufgabe in einer Mathe-Olympiade oder einem ähnlichen Mathematik-Wettbewerb (habe ich früher mal im Internet gefunden) mit folgendem Inhalt (aus der Erinnerung):
Gegeben ist eine Gruppe von 16 Personen (übertragen auf oben wäre also |V|=16). Aus den 16 Personen sollen mehrere Untergruppen zu je 4 Personen (eine vierergruppe wurde m.W. in der Aufgabe als Workshop bezeichnet, übertragen auf oben wäre das k=4) so gebildet werden, daß jedes paar von zwei Personen in mindestens einer Vierergruppe aufeinandertrifft (also jede Person in mindestens einer Untergruppe auf jede andere Person trifft) und die Anzahl der dafür zu bildenden Untergruppen minimal ist. Gesucht war die Anzahl der minimal zu bildenden Untergruppen.
Vielleicht kann sich jemand an diese Aufgabe erinnern?!
Ich suche nicht die Anzahl der Gruppen (bzw Katen) für ein bestimmtes k oder bestimmtes |V|, sondern im allgemeinen Fall.
Wäre wirklich toll, wenn mir jemand weiterhelfen könnte.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:20 Mi 16.06.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
