„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.
Laptörténet interaktív böngészése
← Régebbi szerkesztésÚjabb szerkesztés →
Tartalom törölve Tartalom hozzáadva
VizuálisWikiszöveges
Nincs szerkesztési összefoglaló
Nincs szerkesztési összefoglaló
1. sor: 1. sor:
{{H-lap|könyv=Halmazrendszerek geometriája|előző=Halmazrendszerek geometriája|következő=?}}
{{H-lap|könyv=Halmazrendszerek geometriája|előző=Halmazrendszerek geometriája|következő=?}}


== Nem-elfajuló hipergráf ==


<div style="border: solid 2px #ee0000; background: #ffc676; text-color: black; text-align: justify; margin: 1em; padding: 1em;">
<h4>'''Definíció''': </h4><hr>
: Egy <big>(U,E)</big> 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.
</div>

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ű <big>U</big> halmaz felett <math>2^{2^{n}}</math> db. hipergráf értelmezhető, minthogy ennyi eleme van a <big>℘(U)</big> hatványhalmaz hatványhalmazának. Ha <big>℘(U)</big>-ból eltávolítjuk az üres halmazt, amely az eleme, akkor elemeinek száma eggyel csökken, és egy |<big>℘(U)</big>|-1 = 2<sup>n</sup>-1 -elemű <big>U</big>' halmazt kapunk. Az <big>U</big> feletti, üres halmazt elemként nem tartalmazó hipergráfok épp az <big>U</big>' részhalmazai. Ezek száma így <math>2^{2^{n}-1} = \frac{2^{2^{n}}}{2} = 0.5 \cdot 2^{2^{n}} = 0.5 \cdot 2^{2^{|U|}}</math>. 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 <big>℘(U')</big> részhalmazai, azaz <big>℘(℘(U))</big> elemei csak elemként nem tartalmazhatják ∅-t, de lehet(nek) üres(ek), hiszen ∅∈<big>℘(℘(U))</big>. De csak ez az egy elem lehet üres, azaz <math>2^{2^{|U|}-1}-1 = \frac{2^{2^{|U|}}-2}{2} </math> az <big>U</big> feletti nem-elfajuló és 1 az <big>U</big> feletti teljesen elfajuló hipergráfok száma, a maradék félig elfajulóké pedig <math>2^{2^{|U|}-1} = 0.5 \cdot 2^{2^{|U|}}</math>.


== Illeszkedési sík ==

<div style="border: solid 2px #ee0000; background: #ffc676; text-color: black; text-align: justify; margin: 1em; padding: 1em;">
<h4>'''Definíció''': </h4><hr>
: Egy nem-elfajuló hipergráfot '''illeszkedési sík'''nak 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 '''pont'''oknak is szokás nevezni.
</div>

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


== n-metszőrendszer ==
== n-metszőrendszer ==

A lap 2008. július 12., 17:21-kori változata


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.
A lap eredeti címe: „https://hu.wikibooks.org/w/index.php?title=Szerkesztő:Gubbubu/Halmazrendszerek_geometriája/Hilbert-féle_illeszkedési_síkok&oldid=65456”