„Szerkesztő:Gubbubu/Halmazrendszerek geometriája/Hilbert-féle illeszkedési síkok” változatai közötti eltérés
23. sor: | 23. sor: | ||
: Egy nem-elfajuló hipergráfot '''illeszkedési sík'''nak nevezünk, ha |
: Egy nem-elfajuló hipergráfot '''illeszkedési sík'''nak nevezünk, ha |
||
# Tartóhalmaza tartalmaz legalább három elemet; |
# Tartóhalmaza tartalmaz legalább három elemet; |
||
# Bármely élének van legalább két |
# Bármely élének van legalább két pontja. |
||
: Az illeszkedési síkok csúcsait '''pont'''oknak is szokás nevezni. |
: Az illeszkedési síkok csúcsait '''pont'''oknak is szokás nevezni. |
A lap 2008. július 11., 21:44-kori változata
Nem-elfajuló hipergráf
Definíció:
- Egy (U,E) hipergráfot nem-elfajulónak mondunk, ha szerkezete nem üres, és az üres halmazt sem tartalmazza; ellenkező esetben (azaz ha üres, vagy tartalmazza élként az üres halmazt) elfajulónak mondjuk.
- Egy elfajuló hipergráfot félig elfajulónak mondunk, ha nem üres, és teljesen elfajulónak, ha üres.
Az egyetlen érdekes kérdés ezzel kapcsolatban, hogy egy véges U halmaz felett hány hipergráf elfajuló, illetve nem-elfajuló.
Egy véges, n-elemű U halmaz felett db. hipergráf értelmezhető, minthogy ennyi eleme van a ℘(U) hatványhalmaz hatványhalmazának. Ha ℘(U)-ból eltávolítjuk az üres halmazt, amely az eleme, akkor elemeinek száma eggyel csökken, és egy |℘(U)|-1 = 2n-1 -elemű U' halmazt kapunk. Az U feletti, üres halmazt elemként nem tartalmazó hipergráfok épp az U' részhalmazai. Ezek száma így . Tehát ennyi ∅-t nem tartalmazó hipergráf van egy n-elemű halmaz felett.
Sajnos - ha mondhatjuk ezt - ezek közt még lehet elfajuló, és van is pontosan egy, amelyik üres. Hiszen ℘(U') részhalmazai, azaz ℘(℘(U)) elemei csak elemként nem tartalmazhatják ∅-t, de lehet(nek) üres(ek), hiszen ∅∈℘(℘(U)). De csak ez az egy elem lehet üres, azaz az U feletti nem-elfajuló és 1 az U feletti teljesen elfajuló hipergráfok száma, a maradék félig elfajulóké pedig .
Illeszkedési sík
Definíció:
- Egy nem-elfajuló hipergráfot illeszkedési síknak nevezünk, ha
- Tartóhalmaza tartalmaz legalább három elemet;
- Bármely élének van legalább két pontja.
- Az illeszkedési síkok csúcsait pontoknak is szokás nevezni.
n-metszőrendszer
- Egy hipergráfot n-metszőrendszernek nevezünk, ha bármely két (különböző) él legalább n pontban metszi egymást.
n-átlapolórendszer
- Egy hipergráfot n-átlapolórendszernek nevezünk, ha bármely két (különböző) él legfeljebb n pontban metszi egymást.
Uniform hipergráf
Definíció:
- Egy hipergráfot uniformnak mondunk, ha bármely éle azonos számosságú, azaz az élek által tartalmazott csúcsok kölcsönösen egyértelmű (bijektív) módon megfeleltethetőek egymásnak.
- Véges hipergráf esetén arról van szó, hogy bármely élen azonos, mondjuk k csúcs helyezkedik el. Ilyenkor azt mondjuk, a hipergráf k-uniform.
- A 2-uniform hipergráfokat gráfoknak (pontosabban egyszerű gráfoknak) nevezzük.