Fa (gráfelmélet)

A gráfelméletben a fa egy aciklikus és összekapcsolt gráf . Alakja valójában egy fa ágainak elágazását idézi . Ellentétben az egyszerű fákkal, bináris fákkal, vagy az algoritmuselemzés vagy az analitikus kombinatorika általános fáival, amelyek a fák (grafikonok) beágyazódásai a síkban, a fákat (grafikonokat) néha Cayley fáinak nevezik , mivel Cayley képlete számolja őket .

A fák gyűjteményét erdőnek hívják .

Meghatározás

Intuitív definíció

A grafikon olyan pontok halmazát jelöli, amelyeket csúcsoknak vagy csomópontoknak nevezünk , amelyek vonalakkal kapcsolódnak egymáshoz, vagy nem, éleknek hívva .

Ezért nagyon egyszerű koncepció és nagyon általános modellezési eszköz, amely számos területen hasznos.

• Például egy útitervet egy grafikon segítségével modellezhetünk: a városok a csúcsok, és akkor és csak akkor fogunk két csúcsot összekötni egy vonallal, ha az általuk képviselt városokban van út, amely közvetlenül összeköti őket.
• A közösségi hálózat egy másik példa: a felhasználók a csúcsok, és két felhasználó akkor és csak akkor lesz összekapcsolva, ha mindketten barátok a másikkal.

Vegye figyelembe, hogy a csúcsok elrendezése (hely a térben) nem számít, és még az élek alakja sem kapcsolhatja össze ezeket a csúcsokat (egyenes, görbe stb.). Csak a csúcsok közötti kapcsolat számít.

A fa olyan grafikon, amely kielégíti a következő tulajdonságokat:

• Kapcsolódás: mindig lehetséges az egyik csúcsról a másikra egy élek útján haladni. Az ütemterv esetében ez azt jelenti, hogy mindig lehet közúton egyik városból a másikba haladni.
• Aciklusos: lehetetlen egy csúcsról indulni és visszatérni anélkül, hogy valamikor visszafordulnánk.

Formális meghatározás

A grafikon olyan pár , hogy (S,NÁL NÉL){\ displaystyle (S, A)}

• S{\ displaystyle S}egy tetszőleges nem üres halmaz, amelynek elemeit csúcsoknak vagy csomópontoknak nevezzük .
• NÁL NÉL⊂{{x,y}|x,y∈S,x≠y}{\ displaystyle A \ részhalmaz \ {\ {x, y \} \, | \, x, y \ S-ben, \, x \ neq y \}}. A (z) elemeket éleknek nevezzük .NÁL NÉL{\ displaystyle A}

A fa olyan gráf , hogy (S,NÁL NÉL){\ displaystyle (S, A)}

• (Kapcsolódás) .∀x,y∈S mint például x≠y,∃x1,...,xnem∈S mint például {x,x1},{x1,x2},...,{xnem,y}∈NÁL NÉL{\ displaystyle \ forall x, y \ S-ben {\ text {például}} x \ neq y, \, \ is létezik x_ {1}, \ dots, x_ {n} \ in S {\ text {például} } \ {x, x_ {1} \}, \ {x_ {1}, x_ {2} \}, \ pontok, \ {x_ {n}, y \} \ A-ban
• (Aciklusos) .∀x∈S,∄x1,...,xnem∈S mint például {x,x1},{x1,x2}...,{xnem,x}∈NÁL NÉL{\ displaystyle \ forall x \ in S, \, \ nexists x_ {1}, \ dots, x_ {n} \ in S {\ text {például}} \ {x, x_ {1} \}, \ { x_ {1}, x_ {2} \} \ pontok, \ {x_ {n}, x \} \ az A} -ben

Definíció a véges fák indukciójával

A véges fák esetében, vagyis amikor a csúcsok halmaza véges, van egy alternatív meghatározás. Valóban lehetséges indukcióval meghatározni azon véges fák halmazát, amelyek csúcsa egy adott nem üres E halmazhoz tartozik (véges vagy végtelen):

• ha s az E eleme, akkor ({ s }, ∅) egy fa;
• ha ( S , A ) egy fa, majd ( S ∪ { x }, A ∪ {{ x , s }}) egy fa minden x az E nem tartozó S és s tartozó S  ;
• egyetlen más grafikon sem fa.

Más szavakkal, az a fakészlet, amelynek csúcsa E- hez tartozik, a legkisebb grafikonkészlet, amely megfelel a fenti első két szabálynak.

Szókincs és a hozzá kapcsolódó fogalmak

A fákhoz számos nagyon hasznos fogalom kapcsolódik, amelyek közül néhányat az alábbi táblázat ad meg. Az itt megadott fogalmak valójában mind érvényesek a grafikonok általános keretrendszerében. A táblázatban rögzítünk egy fát ( S, A ).

Fogalom	Intuitív definíció	Formális meghatározás
Szomszédos csúcsok	Két x és y csúcs szomszédos, ha egy él összeköti őket.	x,y∈S mint például {x,y}∈NÁL NÉL{\ displaystyle x, y \ in S {\ text {például}} \ {x, y \} \ in A}
Szomszédos élek	Két szélét egy 1 és egy 2 szomszédos, ha megosztják az egyik vége a közös.	nál nél1,nál nél2∈E mint #nál nél1∪nál nél2≤3{\ displaystyle a_ {1}, a_ {2} \ E-ben {\ text {például}} \ # a_ {1} \ cup a_ {2} \ leq 3}
Egy csúcs mértéke x	Az x- szel szomszédos csúcsok száma .	deg⁡(x)=#{y∈S|{x,y}∈NÁL NÉL}{\ displaystyle \ deg (x) = \ # \ {y \ in S \, | \, \ {x, y \} \ A \}}
Levél növényen	X csúcs, amelynek fokozata 1.	x∈S mint példáuldeg⁡(x)=1{\ displaystyle x \ S-ben {\ text {például}} \ deg (x) = 1}
Belső csúcs	X csúcs, amelynek fokozata szigorúan nagyobb, mint 1.	x∈S mint példáuldeg⁡(x)>1{\ displaystyle x \ S-ben {\ text {például}} \ deg (x)> 1}
Road élek	Több szomszédos élből álló út, amely a végéig helyezkedik el.	nál nél1,...,nál nélnem∈E mint ∀én,nál nélén szomszédos nál nélén+1{\ displaystyle a_ {1}, \ dots, a_ {n} \ E-ben {\ text {például}} \ forall i, a_ {i} {\ text {szomszédos}} a_ {i + 1}}
Két x és y csúcs közötti távolság	Az x-et és y-t összekötő legrövidebb út mérete .	Ha x és y különböznek egymástól, akkor a d ( x, y ) távolság megegyezik min{nem≥1|∃ pálya nál nél1,...,nál nélnem∈NÁL NÉL mint például x∈nál nél1 és y∈nál nélnem}{\ displaystyle \ min \ {n \ geq 1 \, | \, \ létezik {\ text {path}} a_ {1}, \ dots, a_ {n} \ A {\ text {például}} x \ a_ {1} {\ text {és}} y \ -ban a_ {n} \}} és különben a távolság 0.

A fák típusai

Számos fafaj létezik, amelyek különleges esetek lehetnek azoknak a fáknak vagy fáknak, amelyekre szerkezet került.

Kész fa

A véges fa olyan fa, amelynek csúcsainak halmaza véges. Formálisan egy fa ( S, A ) véges, ha S véges kardinalitású.

A következő tulajdonságokat észlelhetjük:

• A véges fa egy összekapcsolt gráf, amelynek csúcsainak száma pontosan egy egységgel meghaladja az élek számát. Más szavakkal, az ( S, A ) gráf akkor és csak akkor egy fa, ha összekapcsolt és | S | = | A | +1.

• A véges fa olyan ciklusok nélküli grafikon, amelynek csúcsainak száma pontosan egy egységgel meghaladja az élek számát. Más szavakkal, az ( S, A ) gráf csak akkor fa, ha aciklusos és | S | = | A | +1.

Abban a konkrét esetben, amikor S az egész számok halmaza 1 és n között, akkor azt mondjuk, hogy a fa ( S, A ) egy Cayley-fa ( n csúcsú).

Helyileg elkészült fa

A helyileg véges fa olyan fa, hogy az egyes csúcsok mértéke véges. Formálisan egy fa ( S, A ) lokálisan véges, ha az S bármelyik x csúcsa esetén a deg ( x ) véges.

A véges fa mindig helyileg véges, de fordítva nem igaz. A helyileg véges fa csúcsainak száma véges vagy megszámlálható.

Legyen egy lokálisan véges fa. Javítsunk ki bármely elemet . Mert tartalmazza az összes távoli csúcsai pontosan a . Összeköttetésével láthatjuk, hogy minden csúcsa az egyikhez tartozik . Más szavakkal T=(S,NÁL NÉL){\ displaystyle T = (S, A)}r∈S{\ displaystyle r \ in S}nem∈NEM{\ displaystyle n \ in \ mathbb {N}}Dnem={x∈S|d(x,r)=nem}{\ displaystyle D_ {n} = \ {x \ in S \, | \, d (x, r) = n \}}nem{\ displaystyle n}r{\ displaystyle r}T{\ displaystyle T}Dnem{\ displaystyle D_ {n}}

S=⋃nem≥0Dnem.{\ displaystyle S = \ bigcup _ {n \ geq 0} D_ {n}.}

Másrészt indukcióval megmutathatjuk, hogy lokálisan véges, hogy minden véges. Tehát a véges halmazok megszámlálható uniója ezért véges vagy megszámlálható. T{\ displaystyle T}nem≥0,Dnem{\ displaystyle n \ geq 0, \, D_ {n}}S{\ displaystyle S}

Gyökeres fa

A gyökeres fa egyszerűen egy fa, amelynek csúcsa a gyökér különleges státuszát hordozza . Formálisan egy gyökeres fa egy hármas ( S , A , r ), ahol ( S, A ) egy fa, és r az S gyöknek nevezett eleme .

Ez az egyszerű gyökérfogalom lehetővé teszi az ős / leszármazott típusú sorrend kialakítását a fa csúcsai között. A gyökeres fák hasznosak egy populáció genealógiájának modellezéséhez.

Fogalom	Intuitív definíció	Formális meghatározás
X csúcs magassága	Az x és az r gyök közötti távolság .	H(x)=d(x,r){\ displaystyle H (x) = d (x, r)}
X csúcs gyermeke (vagy fia )	Az x mellett található csúcs, amelynek magassága megegyezik az x plusz 1 magasságával .	y∈S mint például {x,y}∈NÁL NÉL és H(y)=H(x)+1{\ displaystyle y \ S {\ text {például}} \ {x, y \} \ A {\ text {és}} H (y) = H (x) +1}
Az x csúcs szülője	A csúcs olyan, hogy x a gyermeke.	y∈S mint például {x,y}∈NÁL NÉL és H(y)=H(x)-1{\ displaystyle y \ S-ben {\ text {például}} \ {x, y \} \ A {\ text {és}} H (y) = H (x) -1}
X csúcsból ereszkedő	A szülő / gyermek nemzetségből eredő csúcs x- től kezdődően .	y∈S mint például ∃{x1,x2},{x2,x3},...,{xnem-1,xnem}∈NÁL NÉL{\ displaystyle y \ S-ben {\ text {például}} \ létezik \ {x_ {1}, x_ {2} \}, \ {x_ {2}, x_ {3} \}, \ dots, \ { x_ {n-1}, x_ {n} \} \ A} -ben  mint például x1=x,xnem=y és ∀én,xén a szülője xén+1{\ displaystyle {\ text {például}} x_ {1} = x, \, x_ {n} = y {\ text {és}} \ forall i, \, x_ {i} {\ text {a szülő /} x_ {i + 1}}
X csúcs őse	A csúcs olyan, hogy x leszármazott.	y∈S mint például ∃{x1,x2},{x2,x3},...,{xnem-1,xnem}∈NÁL NÉL{\ displaystyle y \ S-ben {\ text {például}} \ létezik \ {x_ {1}, x_ {2} \}, \ {x_ {2}, x_ {3} \}, \ dots, \ { x_ {n-1}, x_ {n} \} \ A} -ben  mint például x1=y,xnem=x és ∀én,xén a szülője xén+1{\ displaystyle {\ text {például}} x_ {1} = y, \, x_ {n} = x {\ text {és}} \ forall i, \, x_ {i} {\ text {a szülő /} x_ {i + 1}}
Az x csúcsból fakadó él	Él, amely összeköti x- et ezen gyermekek egyikével.	{x,y}∈NÁL NÉL mint például H(y)=H(x)+1{\ displaystyle \ {x, y \} \ A {\ text {-ban, így}} H (y) = H (x) +1}

Címkézett fa

A címkézett fa olyan fa, amelynek csúcsainak (vagy éleinek) van címkéje , vagyis valamilyen nem üres halmaz eleme (gyakran a címkék egész számok vagy valós számok ).

Egy fa mindig kanonikus csúcsjelzéssel rendelkezik: minden csúcs címkeként fogadja magát. Így egy n csúcsú Cayley-fának tekinthetjük az 1 és n közötti egész számokkal injektív módon címkézett fát . Ezzel a kanonikus címkézéssel a csúcsok mindegyikének különböző címkéje van. A címkekoncepció előnye, hogy több különböző csúcsra azonos címkéket lehet adni.

Orientált fa

Az orientált fa az a fa, ahol az élek orientáltak, vagyis irányuk van (az egyik csúcsból indulva a másikhoz érkeznek). Formálisan egy orientált fa olyan pár , hogy (S,NÁL NÉL^){\ displaystyle (S, {\ hat {A}})}

• NÁL NÉL^⊂{(x,y)|x,y∈S,x≠y}{\ displaystyle {\ hat {A}} \ subset \ {(x, y) \, | \, x, y \ S, \, x \ neq y \}}.
• Ha jelöljük, akkor egy fa.NÁL NÉL={{x,y}|(x,y)∈NÁL NÉL^}{\ displaystyle A = \ {\ {x, y \} \, | \, (x, y) \ in {\ hat {A}} \}}(S,NÁL NÉL){\ displaystyle (S, A)}

A gyökeres fának két kanonikus iránya van:

• az élek a gyökerektől legtávolabbi leszármazottaktól a legközelebbi leszármazottakig vannak orientálva. Formálisan vállaljuk .NÁL NÉL^={(x,y)|{x,y}∈NÁL NÉL és H(x)=H(y)+1}{\ displaystyle {\ hat {A}} = \ {(x, y) \, | \, \ {x, y \} \ A {\ text {és}} H (x) = H (y) + 1 \}}
• az élek a gyökérhez legközelebb álló leszármazótól a legtávolabbi leszármazott felé irányulnak. Formálisan vállaljuk .NÁL NÉL^={(x,y)|{x,y}∈NÁL NÉL és H(x)=H(y)-1}{\ displaystyle {\ hat {A}} = \ {(x, y) \, | \, \ {x, y \} \ A {\ text {és}} H (x) = H (y) - 1 \}}

Az irányított fa definíció szerint mindig kapcsolódik (azt is mondjuk, hogy gyengén kapcsolódik ), de nem feltétlenül szorosan kapcsolódik . Valójában az egyetlen erősen összefüggő orientált fa a triviális fa, amelynek csak egy csúcsa van.

Rendezett fa

A rendezett fa egy gyökeres fa, amely minden csúcshoz teljes sorrendet adott meg ennek a csúcsnak a gyermekei számára.

A fák kombinatorikus

Cayley Formulája

Megmutathatjuk, hogy n n - 2 számozott, n csúcsú fa van . Ennek a képletnek a felfedezését egy ideje Arthur Cayley-nek tulajdonítják . Emiatt a fákat grafikonként néha Cayley-fáknak nevezik . A sok igazolások idézzük az egyik, amely használja a Joyal bijekciót  : megszámolni a halmaz elemeit a Cayley fák n csúcsú Joyal létesít bijekciót között , és a készlet térképek a rendszerint jegyezni . Így van  VSnem {\ displaystyle \ {\ mathcal {C}} _ ​​{n} \} VSnem×[[1,nem]]2 {\ displaystyle \ {\ mathcal {C}} _ ​​{n} \ szor [\! [1, n] \!] ^ {2} \} [[1,nem]] {\ displaystyle \ [\! [1, n] \!] \} [[1,nem]] {\ displaystyle \ [\! [1, n] \!] \} [[1,nem]][[1,nem]] {\ displaystyle \ [\! [1, n] \!] ^ {[\! [1, n] \!]} \}

nemnem = Kártya ([[1,nem]][[1,nem]]) = Kártya (VSnem×[[1,nem]]2) = nem2Kártya VSnem.{\ displaystyle n ^ {n} \ = \ {\ text {Card}} \ \ left ([\! [1, n] \!] ^ {[\! [1, n] \!]} \ right) \ = \ {\ text {Card}} \ \ left ({\ mathcal {C}} _ ​​{n} \ szor [\! [1, n] \!] ^ {2} \ right) \ = \ n ^ {2} \, {\ text {Card}} \ {\ mathcal {C}} _ ​​{n}.}

Irányultság

Ha bármelyik r csúcsot választunk egy fában, akkor lehetséges, hogy a fát r- be gyökerezzük , vagyis az összes élét úgy orientáljuk, hogy legyen út az r- től az összes többi csomópontig. Ezután gyökeres fát kapunk .

Fa mint kártya

A fa egy sík gráf  : egy olyan gráf, amely a síkban megrajzolható anélkül, hogy élei érintkeznének, kivéve a végeiket. Az ilyen rajzot néha grafikon beágyazásának is nevezik . A legtöbb síkgrafikon több nem homeomorf beágyazással rendelkezik abban az értelemben, hogy ezek közül legalább kettő esetében nincs a teljes sík felé irányuló homeomorfizmusa, amely beágyazást küldene a másik beágyazásnak: ezeknek a beágyazásoknak az osztályait homeomorfizmusoknak nevezzük. sík térképek . A fa beágyazások homeomorfizmus osztályait (grafikonok) fáknak is nevezzük (sík, általános, katalán). A felsoroláshoz kényelmes, ha gyökérrel, nevezetesen orientált éllel látjuk el őket: ezután gyökeres síkfákról beszélünk . Így az n éllel gyökerező síkfák száma az n- edik katalán szám  :

VSnem=1nem+1(2nemnem)=(2nem)!nem!(nem+1)!.{\ displaystyle C_ {n} = {\ frac {1} {n + 1}} {2n \ select n} = {\ frac {(2n)!} {n! (n + 1)!}}.}

Példa: 3 élű (és 4 csúcsú) fák

A síkfák nincsenek felcímkézve , míg a Cayley-fák (az n csúcsot 1-től n- ig jelölik ). Például két gyökér nélküli és címkézetlen háromélű fa van, az egyiknek 3 fokos csúcsa és 3 levele van (háromágú csillag), a másiknak 2 2 fokos csúcsa és két levele (sora) van.

• A csillag négyféleképpen címkézhető (a 4 lehetőség közül a középső címke szabad megválasztásával a 3 levél címkéinek megválasztása mindig ugyanazon fához vezet). A vonal 4! = 24 módon jelölhető, ekvivalens 2-re 2 (pl. 1234 és 4321 ekvivalens), tehát valójában 12 módon, ami 12 + 4 = 16 = 4 2 3 élű Cayley-fát eredményez.
• A csillag kétféleképpen gyökerezhet: a gyökér lehet a három él bármelyike, mindegy, melyik, a két nem homeomorf választás a befelé (a közép felé) vagy a kimenő él választása. A vonal háromféleképpen gyökerezhet, kiálló vagy visszahúzódó vég vagy középső gerinc, tehát 5 síkfa:

2+3=5.=VS3=14(6.3)=6.!3!4!.{\ displaystyle 2 + 3 = 5 = C_ {3} = {\ frac {1} {4}} {6 \ select 3} = {\ frac {6!} {3! 4!}}.}

A fa ábrázolható úgy, hogy az alján vagy a tetején a gyökérszél eredete van (az informatikában a gyökér gyakran fent látható), a gyökéré pedig teljesen jobbra vagy teljesen balra ( a gyökérszél fölötti ábra a piros pontnál kezdődik és a kék pontnál ér véget).

Unokaöccse jelölése

Egy gyökeres síkfát egyértelműen leírhatunk annak csúcsainak felsorolásával, mindegyiket véges egész sorozattal jelöljük, amelyek testvérükön belül a csúcs őseinek pozíciói: ez az unokaöccs jelölése . A családfa itt használt , mint egy metafora a síkbeli fa: a vertex 2 | 4 | 3 jelöli a 3 rd  fia 4 -én  fia, a 2 nd  fia őse (az ős maga jelölik az üres csomag, megjegyezte ). Megállapodás szerint az ős a gyökérszél kezdeti csúcsa, a gyökérszél végső csúcsa pedig az ős legidősebb fia: mint ilyen, megjegyezzük, hogy 1. A társított szekvencia hossza egy csúcson a magasság (vagy mélysége ), vagyis a csúcs és a gyök kezdete közötti távolság, amely az ősöket képviseli: a metafora követésével az n magasságú csúcs a megalapított populáció n- edik generációjához tartozó egyént képviseli. az ős által. ∅ {\ displaystyle \ scriptstyle \ emptyyset}

Az 5, 3 élű fát tehát az 5 szócsoport írja le

{∅,1,2,3}, {∅,1,11.,2}, {∅,1,2,21}, {∅,1,11.,12.} és {∅,1,11.,111.}.{\ displaystyle \ {\ emptyyset, 1,2,3 \}, ~ \ {\ emptyyset, 1,11,2 \}, ~ \ {\ tyhjyset, 1,2,21 \}, ~ \ {\ emptyyset, 1,11,12 \} ~ {\ text {és}} ~ \ {\ emptyyset, 1,11,111 \}.}

A csúcsok útja lexikográfiai sorrendben ekkor egy fa előtagolt mélységi útvonala (vagy előtag-útvonala), amelyet a számítástechnika adatszerkezetének tekintenek . Ezenkívül a Neveu-jelöléssel érzékeljük, hogy egy síkfa kényelmesen kódolja-e a Galton-Watson-folyamat megvalósulását kihalással: a Galton-Watson-folyamat megvalósításának kódolásával kapott véletlen fát néha Galton-fa -Watson-nak hívják . Semmi sem áll szemben azzal, hogy Neveu jelölése alapján meghatározzunk egy végtelen síkfát, amely lehetővé teszi a Galton-Watson-folyamatok megvalósításainak kódolását, ahol a populáció nem olt ki .

Fa és bomlás

A fák érdekes tulajdonságai miatt, különösen az elméleti számítástechnikában , néha hasznos az általános grafikonokat fákra bontani. Így például a faszélességet úgy definiáljuk, hogy egy fába szervezett csomópontcsoportokat készítünk, és az arboricitást az élek erdőkbe osztásával .

Megjegyzések és hivatkozások

1. Általánosabban véve a nem orientált aciklusos gráfokat, amelyek az elkülönült fák találkozásai, erdőknek nevezzük .
2. vö. Bevezetés az algoritmusok elemzésébe , Robert Sedgewick és Philippe Flajolet, Ch. 6., különösen a 329. oldal.
3. Az itt megadott definíció azt sugallja, hogy egy csúcs nem saját leszármazottja, de néhány definíció tartalmazza ezt az esetet. Ez a megjegyzés továbbra is érvényes az ős fogalmára.
4. Valójában a síkgrafikonokat a gömbbe merítjük, amelyet síknak és végtelen pontnak tekintünk, és megvitatjuk a gömb homeomorfizmusainak létezését, amely beágyazást küld a másik beágyazásba.
5. J. Neveu , „  Fák és Galton-Watson folyamatok  ”, Ann. az IHP-től , vol.  22, n o  21986( online olvasás ) (2. szakasz).

Lásd is

Kapcsolódó cikkek

• Fa (matematika)
• Kombinatorikus bizonyítás  : különbség a bijection és a double counting bizonyítás között
• Kifejezés (logikus)
• A gráfelmélet szószedete
• Gyökeres fa
• Polifa

Bibliográfia

• (en) Martin Aigner és Günter M. Ziegler , bizonyítékok a THE BOOK-ból , Berlin, Springer ,2003, 3 e  . , 240  p. ( ISBN  978-3-540-40460-6 , nyilatkozat BNF n o  FRBNF39082186 ) , p.  141-146
• Philippe Flajolet és Robert Sedgewick , Bevezetés az algoritmusok elemzésébe , Addison-Wesley,1995( ISBN  978-0-201-40009-0 )

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">