Incidenční struktura

Struktura výskytu je  v matematice trojnásobná

kde P  je množina „bodů“, L  je množina „čar“ a  je vztah výskytu . Prvky se nazývají vlajky . Pokud , říkáme, že bod p "leží" na přímce . L lze reprezentovat jako množinu podmnožin P a výskyt I je inkluze ( pokud a pouze tehdy ), ale lze uvažovat abstraktněji.

Struktury incidence zobecňují letadla (takový jako affine , projective a Möbius letadla ), jak může být viděno z axiomatických definic těchto rovin. Incidenční struktury také zobecňují geometrické struktury vyšších rozměrů; konečné struktury jsou někdy označovány jako konečné geometrie .

Srovnání s jinými strukturami

Zobrazení incidenční struktury může vypadat jako graf , ale v grafech má hrana pouze dva koncové body, zatímco čára v incidenční struktuře může dopadat do více než dvou bodů. Incidenční struktury jsou tedy hypergrafy .

V incidenční struktuře neexistuje žádný koncept bodu ležícího mezi dvěma dalšími body. Pořadí bodů na přímce není definováno. Porovnejte s uspořádanou geometrií , která má vztah ležící mezi.

Dvojitá struktura

Pokud si vyměníme role „bodů“ a „čar“ ve struktuře incidence

C = ( P , L , I )

získat dvojí strukturu

C * = ( L , P , I *),

kde I * je binární relace, inverzní k I . To je jasné

C ** = C.

Tato operace je abstraktní verzí projektivní duality .

Struktura C , která je izomorfní ke své duální struktuře C *, je považována za samoduální .

Korespondence s hypergrafy

Na každý hypergraf nebo množinový systém lze nahlížet jako na incidenční strukturu, ve které univerzální množina hraje roli „bodů“, odpovídající soustava množin hraje roli „čar“ a incidenční relací je členství „∈“. Naopak na libovolnou strukturu incidencí lze nahlížet jako na hypergraf.

Příklad: Fano letadlo

Zejména nech

P  = {1, 2, 3, 4, 5, 6, 7}, L  = { {1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7} , {3,5,6} }.

Odpovídající struktura dopadu se nazývá Fanova rovina .

Čáry jsou přesně podmnožiny bodů, které se skládají ze tří bodů, jejichž popisky jsou doplněny na nulu součtem nim .

Geometrické znázornění

Strukturu dopadu lze modelovat pomocí bodů a křivek v euklidovské geometrii se standardním geometrickým zahrnutím jako vztahem dopadu. Některé incidenční struktury lze znázornit pomocí bodů a čar, ale například Fano plocha takové znázornění nemá.

Leviho graf struktury výskytu

Libovolná struktura výskytu C odpovídá bipartitnímu grafu , nazývanému Leviho graf , nebo strukturnímu grafu incidence. Protože každý bipartitní graf může být obarven dvěma barvami, mohou být vrcholy Leviho grafu obarveny bílou a černou barvou, kde černé vrcholy odpovídají bodům a bílé vrcholy odpovídají čarám C . Okraje tohoto grafu odpovídají příznakům (dvojice incidentů bod/čára) struktury výskytu.

Příklad: Earl of Heawood

Leviho graf Fanoovy roviny je Heawoodův graf . Protože je Heawoodův graf souvislý a vertexově tranzitivní , existuje automorfismus (jako je odraz kolem svislé osy na obrázku vpravo), který vyměňuje bílé a černé vrcholy. To znamená, že letadlo Fano je samoduální.

Viz také

Odkazy