„Szerkesztő:Gubbubu/Halmazrendszerek geometriája/Hilbert-féle illeszkedési síkok” változatai közötti eltérés

A Wikikönyvekből, a szabad elektronikus könyvtárból.
Tartalom törölve Tartalom hozzáadva
Nincs szerkesztési összefoglaló
1. sor: 1. sor:
{{H-lap|könyv=Halmazrendszerek geometriája|előző=|következő=?}}
{{H-lap|könyv=Halmazrendszerek geometriája|előző=Halmazrendszerek geometriája|következő=?}}


== Nem-elfajuló hipergráf ==
== Nem-elfajuló hipergráf ==

A lap 2008. július 12., 16:12-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
  1. Tartóhalmaza tartalmaz legalább három elemet;
  2. Bármely élének van legalább két pontja.
Az illeszkedési síkok csúcsait pontoknak is szokás nevezni.

Az illeszkedési síkok természetesen nem-elfajuló hipergráfok.

n-metszőrendszer

  1. Egy nem üres szerkezetű (nem teljesen-elfajuló) 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

  1. Egy hipergráfot n-átlapolórendszernek nevezünk, ha bármely két (különböző) él legfeljebb n pontban metszi egymást.

Például 1-átlapolórendszerről beszélünk, ha bármely két él legfeljebb egy csúcsban metszi egymást, 2-átlapolórendszerről, ha bármely két él legfeljebb két pontban metszi egymást, s. í. t.

Hilbert-féle illeszkedési sík

Egy illeszkedési síkot Hilbert-féle illeszkedési síknak (HIS) mondunk, ha bármely két (különböző) él legfeljebb egy pontban metszi egymást. A Hilbert-féle illeszkedési síkok éleit egyeneseknek is mondjuk.

Természetesen igaz: Egy hipergráf akkor és csak akkor HIS, ha

  1. illeszkedési sík
  2. 1-átlapolórendszer

Féllineáris illeszkedési sík

Egy illeszkedési síkot féllineárisnak mondunk (féllineáris illeszkedési sík, FIS), ha bármely két (különböző) csúcshoz pontosan egy él található a szerkezetben, amely őket tartalmazza.

Tételke: Minden FIS egyben HIS.

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.