Mediánový graf

V teorii grafů je mediánový graf neorientovaný graf , ve kterém libovolné tři vrcholy a , b a c mají jeden medián  , vrchol m ( a , b , c ), který patří k nejkratším cestám mezi každou dvojicí vrcholů a , b a c .

Koncept mediánových grafů byl studován již dlouhou dobu, například Birkhoffem a Kissem ( Birkhoff, Kiss 1947 ) nebo (výslovněji) Avannem ( Avann 1961 ), ale první článek s názvem „Median graphs“ se objevil v roce 1971 ( Nebesk'y 1971 ). Jak píší Chang Graham a Saks, "mediánové grafy přirozeně vznikají při studiu uspořádaných množin a diskrétních distributivních svazů a mají rozsáhlou literaturu." 1] Ve fylogenetice je Bunemanův graf reprezentující všechny evoluční stromy s maximální pravděpodobností středním grafem. [2] Mediánové grafy se objevují i ​​v teorii sociální volby  — pokud má soubor možností strukturu mediánového grafu, lze jednoznačně určit preferenci většiny z nich. [3]

Přehled mediánových grafů lze nalézt v Klavžar, Mulder, 1999 , Bandelt, Chepoi, 2008 a Knuth, 2008 .

Příklady

Libovolný strom je mediánový graf. [4] Ve stromu je spojení tří nejkratších cest mezi dvojicemi tří vrcholů a , b a c buď samotnou cestou, nebo podstromem tvořeným třemi cestami ze stejného centrálního vrcholu třetího stupně . Pokud je sjednocení tří cest samo cestou, medián m ( a , b , c ) se rovná jednomu z vrcholů a , b nebo c , podle toho, který vrchol je mezi dvěma dalšími na cestě. Pokud strom vytvořený spojením cest není cestou, medián bude centrálním uzlem podstromu.

Mříže jsou dalším příkladem mediánových grafů . V mřížkovém grafu lze souřadnice mediánu m ( a , b , c ) nalézt jako medián souřadnic vrcholů a , b a c . Naopak se ukazuje, že je možné uspořádat vrcholy na celočíselné mřížce tak, že mediány lze vypočítat jako mediány souřadnic . [5]

Rámcové grafy [6] , rovinné grafy, ve kterých jsou všechny vnitřní plochy čtyřúhelníky a všechny vnitřní vrcholy mají čtyři nebo více dopadajících hran, jsou další podtřídou mediánových grafů. [7] Polyomino  je speciální případ rámcových grafů, a proto tvoří také mediánový graf.

Simplexní graf κ( G ) libovolného neorientovaného grafu G má vrchol pro každou kliku (úplný podgraf) G a dva vrcholy jsou spojeny hranou, pokud se odpovídající kliky liší pouze o jeden vrchol. Medián daných tří klik lze vytvořit pomocí pravidla většiny , které vám umožňuje určit, které vrcholy kliky zahrnout. Simplexní graf je mediánový graf, ve kterém toto pravidlo určuje medián každé trojice vrcholů.

Žádný cyklus délky než čtyři nemůže být středním grafem, protože každý takový cyklus má tři vrcholy a , b a c , které jsou spojeny třemi nejkratšími cestami, které nemají žádné průsečíky.

Ekvivalentní definice

V libovolném grafu se pro libovolné dva vrcholy a a b minimální počet hran mezi nimi nazývá vzdálenost , která je označena jako d ( x , y ). Interval vrcholů ležících na nejkratší cestě mezi aab je definován jako

I ( a , b ) = { v | d ( a , b ) = d(a, v) + d(v, b) }.

Mediánový graf je definován jako graf pro libovolné tři vrcholy a , b a c , jejichž intervaly se protínají v jednom bodě:

Pro všechna a , b a c | I ( a , b ) ∩ I ( a , c ) ∩ I ( b , c )| = 1.

Podobně pro libovolné tři vrcholy a , b a c lze najít vrchol m ( a , b , c ) takový, že nevážené vzdálenosti v grafu splňují rovnosti

a m ( a , b , c ) je jediný vrchol, pro který to platí.

Mediánové grafy lze také definovat jako řešení problémů 2-splnitelnosti, jako redukci hyperkrychle, jako grafy konečných mediánových algeber, jako Bunemanovy grafy Halleyových rozdělovacích systémů a jako grafy windex 2. Viz sekce níže.

Distribuované svazy a mediánové algebry

V teorii mřížek má graf konečné mřížky vrchol pro každý prvek mřížky a hranu pro každou dvojici prvků krycího vztahu mřížky. Svazy jsou obvykle reprezentovány vizuálně jako Hasseovy diagramy , což jsou kresby grafů svazů. Ukázalo se, že tyto grafy, zejména pro distributivní svazy , úzce souvisejí s mediánovými grafy.

V distributivní Birkhoffově mřížce je samoduální ternární operace mediánu [8]

m ( a , b , c ) = ( a ∧ b ) ∨ ( a ∧ c ) ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( a ∨ c ) ∧ ( b ∨ c ),

splňuje některé klíčové axiomy, které jsou charakteristické pro běžné mediány čísel v intervalu od 0 do 1 a mediánové algebry :

Distributivní zákon může být nahrazen asociativním: [9]

Mediánovou operaci lze také použít k definování konceptu intervalů pro distribuované svazy:

I ( a , b ) = { x | m(a, x, b) = x } = { x | a ∧ b ≤ x ≤ a ∨ b }. [deset]

Graf konečné distributivní mřížky má hranu mezi vrcholy a a b , když I ( a , b ) = { a , b }. Pro libovolné dva vrcholy a a b tohoto grafu se interval I ( a , b ) definovaný z hlediska teorie svazů skládá z vrcholů nejkratší cesty z a do b , a to se shoduje s intervaly z teorie grafů definovanými dříve. Pro libovolné tři prvky mřížky a , b a c je m ( a , b , c ) jediným průsečíkem tří intervalů I ( a , b ), I ( a , c ) a I ( b , c ). [11] Graf libovolné konečné distribuované mřížky je tedy mediánovým grafem. Naopak, pokud mediánový graf G obsahuje dva vrcholy 0 a 1 tak, že jakékoli jiné vrcholy leží na nejkratší cestě mezi těmito dvěma (ekvivalentně m (0, a ,1) = a pro všechna a ), pak můžeme definovat distribuovaný mřížku, ve které a ∧ b = m ( a ,0, b ) aa ∨ b = m ( a ,1, b ), a G bude graf této mřížky. [12]

Duffus a Rival ( Duffus, Rival 1983 ) popisují distributivní mřížkové grafy jako zachování redukčního průměru hyperkrychlí. Obecně platí, že jakýkoli mediánový graf generuje ternární operaci m , která splňuje zákony idempotence, komutativnosti a distributivity, ale možná bez jediného prvku distribuované mřížky. Jakákoli ternární operace na konečné množině, která splňuje tyto tři vlastnosti (ale nemusí mít nutně prvky 0 a 1), generuje mediánový graf. [13]

Konvexní množiny a Halleyovy rodiny

Ve středním grafu se o množině vrcholů S říká , že je konvexní , jestliže pro libovolné dva vrcholy aab , které patří S , je celý interval I ( a , b ) podmnožinou S. Ekvivalentně, podle dvou výše uvedených definic intervalů, S je konvexní, pokud obsahuje nějakou nejkratší cestu mezi dvěma vrcholy, nebo pokud obsahuje medián jakýchkoli tří bodů, z nichž dva leží v S . Všimněte si, že průsečík libovolné dvojice konvexních množin je sám o sobě konvexní. [čtrnáct]

Konvexní množiny v mediánovém grafu mají Halleyovu vlastnost : je-li F libovolná rodina párově se protínajících konvexních množin, pak všechny množiny F mají společný bod. [15] Nechť tedy F má pouze tři konvexní množiny S , T a U . Nechť a  jsou průsečíky dvojice S a T , b  průsečíky dvojice T a U a c  průsečíky dvojice S a U . Potom jakákoli nejkratší cesta z a do b musí ležet uvnitř T kvůli konvexitě a stejně tak jakákoli nejkratší cesta mezi libovolnými dvěma páry vrcholů musí ležet uvnitř dvou dalších množin, ale m ( a , b , c ) patří do cesty mezi všemi třemi dvojicemi vrcholů, takže leží uvnitř všech tří množin. Pokud F obsahuje více než tři konvexní množiny, výsledek se získá indukcí počtu množin — libovolnou dvojici množin v F lze nahradit jejich průnikem, čímž se výsledné množiny párově protínají.

Sady _ _

W uv = { w | d ( w , u ) < d ( w , v )},

které jsou definovány pro každou hranu uv grafu. Zjednodušeně řečeno, W uv se skládá z vrcholů, které jsou blíže u než v , nebo ekvivalentně z vrcholů w , pro které nejkratší cesta z v do w prochází u . Abychom ukázali, že W uv je konvexní, předpokládejme, že w 1 w 2 … w k  je libovolná nejkratší cesta začínající a končící uvnitř W uv . Pak w 2 musí také ležet uvnitř W uv , jinak dva body m 1 = m ( u , w 1 , w k ) a m 2 = m ( m 1 , w 2 … w k ) budou dva různé mediány u , w 1 , a w k , což je v rozporu s definicí mediánového grafu, ve kterém je medián z definice jedinečný. Každý vrchol na nejkratší cestě mezi dvěma vrcholy W uv tedy také leží ve W uv , takže W uv obsahuje všechny nejkratší cesty mezi vrcholy, což je jedna z definic konvexity.

Halleyova vlastnost pro množiny W uv hraje klíčovou roli při popisu mediánových grafů jako problému 2-splnitelnosti.

2-splnitelnost

Mediánové grafy úzce souvisejí se sadami řešení úloh 2-splnitelnosti , které lze použít k popisu těchto grafů a které lze použít k zobrazení souvislosti s mapováním hyperkrychle se zachováním sousedství. [16]

Instance 2-satisfiability se skládá ze sady booleovských proměnných a kolekce tvrzení , omezení na některé dvojice proměnných, aby se zabránilo některým kombinacím hodnot. Typicky jsou takové problémy vyjádřeny v konjunktivní normální formě , ve které je každý výrok vyjádřen disjunkcí a celá množina omezení je vyjádřena konjunkcí výroků, např.

Řešením takové instance je přiřadit skutečné hodnoty, aby byla splněna všechna tvrzení, nebo ekvivalentně to, že konjunktivní tvrzení v normálním tvaru vytvářejí skutečné hodnoty při dosazení hodnot. Rodina všech řešení má přirozenou strukturu mediánové algebry, kde medián tří řešení je tvořen volbou většinové hodnoty tří hodnot. Je snadné přímo ověřit, že tento medián nemůže porušovat tvrzení. Tato řešení tedy tvoří mediánový graf, ve kterém jsou sousedé každého řešení tvořeni negací množiny proměnných, z nichž všechny jsou všechny hodnoty v množinách buď stejné, nebo se nerovnají.

Naopak libovolný mediánový graf G lze reprezentovat jako množinu řešení instance problému 2-splnitelnosti. Abychom takovou reprezentaci našli, vytvoříme instanci problému 2-splnitelnosti, ve kterém každá proměnná popisuje směr jedné z hran grafu (přiřazení směru hraně vede k orientovaným grafům) a každé omezení obsahuje dva směrované oblouky, pouze pokud existuje vrchol v , pro který oba oblouky leží na nejkratší cestě z ostatních vrcholů k v . Každý vrchol v grafu G odpovídá řešení případu problému 2-splnitelnosti, ve kterém jsou všechny oblouky nasměrovány k v . Každé řešení instance je třeba získat z nějakého vrcholu v tímto způsobem, kde v  je společný průnik množin W uw pro oblouky směřující z w do u . Tento společný průnik existuje díky Halleyově vlastnosti množin W uw . Řešení instance tohoto problému 2-splnitelnosti tedy odpovídají jedna ku jedné vrcholům grafu G .

Hypercube reduction

Redukce grafu G  je zobrazení grafu G do jednoho z jeho podgrafů se zachováním sousedství. [17] Přesněji jde o homomorfismus φ od G k sobě samému, ve kterém platí φ( v ) = v pro každý vrchol v v podgrafu φ(G). Obraz zmenšení se nazývá zmenšení grafu G . Redukce jsou příklady krátkých zobrazení : vzdálenost mezi φ( v ) a φ( w ) pro libovolné v a w je nanejvýš vzdálenost mezi v a w a tyto vzdálenosti jsou stejné, pokud oba vrcholy v a w patří k φ( G ). Rukce tedy musí být izometrickým podgrafem grafu G : vzdálenosti v redukci se rovnají odpovídajícím vzdálenostem v G .

Jestliže G je mediánový graf a a , b a c  jsou tři libovolné vrcholy redukce φ( G ), pak vrchol φ( m ( a , b , c )) musí být mediánem a , b a c , a proto se musí rovnat m ( a , b , c ). φ( G ) tedy obsahuje mediány všech trojic vrcholů a musí to být mediánový graf. Jinými slovy, rodina mediánových grafů je pod operací redukce uzavřena . [osmnáct]

Hyperkrychlový graf , ve kterém vrcholy odpovídají všem možným k - bitovým vektorům a ve kterém jsou dva vrcholy spojeny, pokud se odpovídající vektory liší o jediný bit, je speciálním případem k - rozměrného mřížkového grafu, a tedy mediánovým grafem. Medián tří bitových vektorů a , b a c lze vypočítat tak , že se vezme většinová hodnota bitů a , b a c . Protože grafy mediánu jsou při operaci redukce uzavřeny a zahrnují hyperkrychle, jakákoli redukce hyperkrychle je graf mediánu.

Naopak jakýkoli mediánový graf musí být zmenšením hyperkrychle. [19] To je patrné z výše uvedeného spojení mezi grafy mediánu a problémem 2-splnitelnosti. Nechť G představuje řešení instance problému 2-splnitelnosti. Bez ztráty obecnosti lze tento případ formulovat tak, že žádné dvě proměnné nejsou vždy stejné nebo nestejné ve všech řešeních. Pak prostor všech přiřazení hodnot k proměnným tvoří hyperkrychli. Pro jakýkoli výrok vytvořený disjunkcí dvou proměnných nebo jejich negací, v instanci problému 2-splnitelnosti, lze vytvořit redukci hyperkrychle, ve které je přiřazení proměnných, které porušuje toto tvrzení, mapováno na přiřazení proměnných, ve kterých obě proměnné splňují příkaz, ale nemění ostatní proměnné . Složení takto konstruovaných redukcí pro každý výrok vede k redukci hyperkrychle do prostoru řešení instance problému, a tedy k zobrazení grafu G jako zmenšení hyperkrychle. Zejména grafy mediánu jsou izometrické vůči podgrafům hyperkrychle, a jsou proto částečnou krychlí . Ne všechny dílčí krychle jsou však grafy mediánu. Například cyklus se šesti vrcholy je částečná krychle, ale ne mediánový graf.

Imrich a Klavžar ( Imrich, Klavžar 1998 ) píší, že izometrické vnoření mediánového grafu do hyperkrychle lze sestrojit v čase O( m log n ), kde n a m  jsou počty vrcholů a hran grafu. [dvacet]

Grafy bez trojúhelníků a rozpoznávací algoritmy

Problémy kontroly, zda je graf medián a zda graf obsahuje trojúhelníky , jsou dobře prostudovány a jak poznamenávají Imrich, Klavžar a Mulder (1999 ), jsou v určitém smyslu výpočetně ekvivalentní. [21] Nejznámější čas pro kontrolu, zda graf obsahuje trojúhelníky, což je O( m 1,41 ), [22] lze tedy použít jako odhad času ke kontrole, zda je graf medián, a případného pokroku v grafu. problém rozpoznávání mediánových grafů povede k pokroku v algoritmech pro určování trojúhelníků v grafech.

Abychom dokázali ekvivalenci v jednom směru, předpokládejme, že máme graf G a chceme zkontrolovat, zda obsahuje trojúhelníky. Vytvořme další graf H z G , mající jako vrcholy množinu nuly, jednoho nebo dvou sousedních vrcholů grafu G . Dvě takové množiny sousedí v H , pokud se liší pouze jedním vrcholem. Jako alternativní popis lze H vytvořit rozdělením každé hrany G na dvě a přidáním nového vrcholu spojeného se všemi vrcholy původního grafu G. Tento graf H je částečnou krychlí podle konstrukce, ale bude medián pouze tehdy, když G neobsahuje trojúhelníky - pokud a , b a c tvoří trojúhelník v G , pak { a , b }, { a , c } a { b , c } nemají mediány v H , protože takový medián by musel odpovídat množině { a , b , c }, ale množiny tří nebo více vrcholů G netvoří vrcholy v H . G tedy neobsahuje trojúhelníky právě tehdy, když H je mediánový graf. V případě, že G neobsahuje trojúhelníky, H je jeho simplexní graf . Algoritmus pro efektivní kontrolu, zda H je mediánový graf, pomocí této konstrukce, lze použít ke kontrole nepřítomnosti trojúhelníků v grafu G . Taková transformace zachovává výpočetní složitost problému, protože velikost H je úměrná velikosti G .

Redukce v opačném směru, od hledání trojúhelníků ke kontrole, zda je graf medián, je složitější a závisí na popsaném algoritmu rozpoznávání mediánu grafu ( Hagauer, Imrich, Klavžar 1999 ), který testuje některé nezbytné podmínky pro mediánový graf v téměř lineárním čas. Nový klíčový krok využívá prohledávání do šířky k rozložení grafu na úrovně podle jejich vzdálenosti od libovolně zvoleného kořene, čímž se vytvoří graf, ve kterém dva vrcholy sousedí, pokud mají společného souseda v předchozí úrovni, a hledání v těchto grafech se vyskytují trojúhelníky. Medián každého takového trojúhelníku musí být společným sousedem tří vrcholů trojúhelníku. Pokud takový soused neexistuje, není graf mediánem. Pokud jsou nalezeny všechny trojúhelníky a všechny mají mediány a předchozí algoritmus určí, že graf splňuje ostatní podmínky pro mediánové grafy, pak to musí být medián. Všimněte si, že tento algoritmus vyžaduje nejen kontrolu nepřítomnosti trojúhelníků, ale také výčet trojúhelníků v grafu úrovní. V libovolném grafu vyžaduje výčet trojúhelníků čas Ω( m 3/2 ), protože některé grafy mají tolik trojúhelníků. Hagauer (Hagauer et al.) však ukázal, že počet trojúhelníků, které se vyskytují v hladinových grafech, je téměř lineární, což Alonovi (Alon et al.) umožnilo použít k nalezení trojúhelníků techniku ​​rychlého násobení matic.

Evoluční stromy, Bunemanovy grafy a Halleyovy rozdělovací systémy

Fylogenetika  je odvození fylogenetických stromů z pozorovaných charakteristik druhu . Takové stromy musí mít pohledy v různých vrcholech a mohou obsahovat další skryté vrcholy , ale skryté vrcholy musí mít tři nebo více dopadajících hran a musí být označeny charakteristikami. Charakteristiky jsou binární , pokud mají pouze dvě možné hodnoty, a soubor druhů a jejich charakteristik vykazuje dokonalou evoluční historii , pokud existuje evoluční strom, ve kterém vrcholy (druhy a skryté vrcholy) označené jakoukoli konkrétní charakteristikou tvoří souvislý podstrom. Pokud strom s dokonalou vývojovou historií není možný, je často žádoucí najít strom s maximální pravděpodobností nebo ekvivalentně, aby se minimalizoval počet případů, kdy koncové body okrajů stromu mají různé charakteristiky, a to sečtením přes všechny okraje. a přes všechny vlastnosti.

Buneman ( 1971 ) popsal metodu pro odvození dokonalých evolučních stromů pro binární jevy, pokud existují. Jeho metoda je přirozeným způsobem zobecněna ke konstrukci mediánového grafu libovolného souboru druhů a binárních charakteristik a tento graf se nazývá mediánová síť nebo Bunemanův graf [23] a jedná se o fylogenetickou síť . Do Bunemanova grafu lze vložit jakýkoli evoluční strom s maximální pravděpodobností v tom smyslu, že okraje stromu sledují cesty v grafu a počet změn hodnot charakterizace na okraji stromu se rovná počtu odpovídajících cest. Bunemanův graf je strom právě tehdy, když existuje dokonalá historie vývoje. K tomu dochází, když neexistují dvě neslučitelné charakteristiky, pro které jsou pozorovány všechny čtyři kombinace hodnot.

Abychom vygenerovali Bunemanův graf pro sadu druhů a prvků, nejprve se zbavíme nadbytečných prvků, které jsou k nerozeznání od některých jiných prvků, a od nadbytečných prvků, které se vždy shodují s některými jinými prvky. Poté vytvoříme skrytý vrchol pro jakoukoli kombinaci charakteristických hodnot, takže jakékoli dvě hodnoty existují ve známých formách. V zobrazeném příkladu jsou malé myši s hnědým ocasem, malé myši se stříbrným ocasem, malé myši s hnědým ocasem, velké myši s hnědým ocasem a velké myši se stříbrným ocasem. Metoda Bunemanova grafu vytvoří skrytý vrchol odpovídající neznámému druhu malých stříbrnoocasých myší, protože jakákoliv kombinace párů (malá a stříbřitá, malá a ocasá a stříbřitá a ocasá) se objevuje u některých jiných druhů. Metoda však nepředpokládá existenci velkých hnědých anuranů, protože neexistuje žádný druh velkých a zároveň anuranů. Po definování skrytých vrcholů vytvoříme hrany mezi každou dvojicí pohledů nebo skrytými vrcholy, které se liší v jedné charakteristice.

Množinu binárních charakteristik lze ekvivalentně popsat jako systém oddílů , rodin množin s vlastností, že doplněk libovolné množiny v rodině patří do rodiny. Tento rozdělovací systém představuje sadu pro každou hodnotu prvku, která se skládá z druhů, které mají tuto hodnotu. Pokud jsou zahrnuty skryté vrcholy, výsledný rozdělovací systém má vlastnost Halley  — žádné párové průniky podrodin nejsou prázdné. Mediánové grafy lze v jistém smyslu považovat za deriváty Halleyových dlaždicových systémů — dvojice ( W uv , W vu ) definované pro každou hranu uv mediánového grafu tvoří Halleyovu dlaždicovou soustavu, takže pokud konstrukce Bunemanova grafu Pokud je na tento systém aplikován, skryté vrcholy nejsou potřeba a výsledkem bude původní graf. [24]

Bandelt , Forster, Sykes, Richards, 1995 a Bandelt, Macaulay, Richards, 2000 popisují techniku ​​pro zjednodušení ručního výpočtu Bunemanových grafů a ukazují použití tohoto konstruktu k vizuální reprezentaci genetických vztahů lidí.

Další vlastnosti

Poznámky

  1. ↑ 1 2 3 Chung, Graham, Saks, 1987 .
  2. ↑ Buneman, 1971 , Šaty, Hendy, Huber, Moulton, 1997 , Šaty, Huber, Moulton, 1997 .
  3. ↑ Bandelt, Barthélémy, 1984 , Day, McMorris, 2003 .
  4. ↑ Imrich, Klavžar, 2000 , Vyjádření 1.26, s. 24.
  5. ↑ To bezprostředně vyplývá z vlastnosti redukce hyperkrychle mediánových grafů, jak je popsáno níže.
  6. ↑ A. V. Karzanov. Rozšíření konečných metrik a problém umístění zařízení // Proceedings of the ISA RAS. - 2007. - T. 29 . - S. 225-244 .
  7. ↑ Soltan, Zambitskii, Prisˇacaru, 1973 , Chepoi, Dragan, Vaxès, 2002 , Chepoi, Fanciullini, Vaxès, 2004 .
  8. ↑ Birkhoff, Kiss, 1947 připisují definici této operace článku G. Birkhoffa. Teorie mřížky. - Americká matematická společnost, 1940. - S. 74 . .
  9. ↑ Knuth, 2008 , s. 65 a cvičení 75, 76 na stranách 89-90. Knuth tvrdí, že neexistuje žádný jednoduchý důkaz, že asociativita implikuje distributivitu.
  10. ↑ Ekvivalence dvou výrazů v této rovnosti, jednoho z hlediska operace mediánu a druhého z hlediska operací mřížky a nerovnosti, je věta 1 v Birkhoff a Kiss ( Birkhoff, Kiss 1947 ).
  11. ↑ Birkhoff, Kiss, 1947 , věta 2.
  12. ↑ Birkhoff, Kiss, 1947 , s. 751.
  13. ↑ Avann, 1961 .
  14. ↑ Knuth, 2008 nazývá takovou množinu ideálem , ale konvexní množina v distribuovaném mřížkovém grafu není totéž jako mřížkový ideál .
  15. ↑ Imrich, Klavžar, 2000 , Věta 2.40, s. 77.
  16. ↑ Bandelt, Chepoi, 2008 , prohlášení 2.5, s.8; Chung, Graham, Saks, 1989 ; Feder, 1995 ; Knuth, 2008 , Věta S, s. 72.
  17. ↑ Peklo, 1976 .
  18. ↑ Imrich, Klavžar, 2000 , vyjádření 1.33, s. 27.
  19. ↑ Bandelt, 1984 ; Imrich, Klavžar, 2000 , Věta 2.39, s.76; Knuth, 2008 , s. 74.
  20. ↑ Technikou, která vrcholí v lemmatu 7.10 na straně 218 článku, je použití algoritmu Chiba a Nishizekiho ( Chiba, Nishizeki 1985 ) k získání seznamu všech cyklů délky 4 v grafu G , a který vytvoří graf, který má hrany jako vrcholový graf G a jako hrany své protilehlé strany cyklu 4 hran. Propojené komponenty těchto grafů se používají k vytvoření souřadnic hyperkrychle. Ekvivalentním algoritmem je Knuthův ( Knuth 2008 ), Algorithm H, str. 69.
  21. ↑ Algoritmus rozpoznání mediánu grafu viz Jha, Slutzki, 1992 , Imrich, Klavžar, 1998 a Hagauer, Imrich, Klavžar, 1999 . Algoritmus rozpoznávání grafů bez trojúhelníků viz Itai, Rodeh, 1978 , Chiba, Nishizeki, 1985 a Alon, Yuster, Zwick, 1995 .
  22. ↑ Alon, Yuster, Zwick, 1995 . Algoritmus je založen na rychlém násobení matic . Zde m  je počet hran v grafu a velké "O" skrývá velký konstantní faktor. Nejlepší praktický algoritmus rozpoznávání trojúhelníků vyžaduje O( m 3/2 ) času. Pro rozpoznání mediánu grafu lze časové omezení vyjádřit buď pomocí m nebo n (počet vrcholů), jako je m = O( n log n ).
  23. ↑ Mulder, Schrijver, 1979 popsal verzi této metody pro systémy prvků nevyžadujících skryté vrcholy, zatímco Barthélémy, 1989, poskytl plnou verzi. Bunemanovy počty jsou pojmenovány v Dress, Hendy, Huber, Moulton, 1997 a Dress, Huber, Moulton, 1997 .
  24. ↑ Mulder, Schrijver, 1979 .
  25. ↑ Škrekovski, 2001 .
  26. ↑ Mulder, 1980 .

Poznámky

Odkazy