Lexikografická šířka první hledání

Lexikografické prohledávání do šířky ( LBFS nebo Lex-BFS ) je algoritmus pro uspořádání vrcholů grafu .  Algoritmus se liší od algoritmu prohledávání do šířky a poskytuje uspořádanější[ neznámý výraz ] posloupnost vrcholů v grafu.

Lexikografický algoritmus prohledávání šířky je založen na myšlence podmnožin a byl poprvé vyvinut Rose, Tarjan a Luker (1976). Podrobnější přehled tématu poskytl Corneil (2004) [1] . Lexikografické prohledávání šířky se používá jako součást jiných grafických algoritmů, např . rozpoznávání akordických grafů , plně rozdělené vybarvování grafů .

Popis algoritmu

Aby algoritmus fungoval, je nutné určit vrchol grafu, od kterého začíná procházení. Popis algoritmu je následující:

• Inicializujte posloupnost množin vrcholů Σ skládající se z jedné množiny obsahující všechny vrcholy grafu.
• Inicializujte prázdnou výstupní sekvenci vrcholů.
• Pokud je Σ neprázdné:
  • Vezměte vrchol v z první množiny v Σ a odstraňte jej z množiny.
  • Pokud je první množina v Σ prázdná, odstraňte ji z Σ .
  • Přidejte v na konec sekvence výstupních vrcholů.
  • Pro každý vw edge :
    • Definujte množinu S v Σ, která obsahuje w .
    • Pokud množina S při zpracování v ještě nebyla rozdělena , vytvořte novou prázdnou množinu T a umístěte ji před S v Σ.
    • Přesuňte vrchol w z S do T a pokud je S prázdné, odstraňte jej z Σ.

Každý vrchol je zpracován jednou, každá hrana je testována pouze při zpracování jeho dvou vrcholů a (za předpokladu, že zpracování operací v posloupnosti množin Σ trvá konečný čas) každá iterace vnitřní smyčky trvá konečnou dobu. Časová složitost algoritmu je tedy lineární a je .

Algoritmus se nazývá lexikografické prohledávání do šířky, protože výsledné pořadí je podobné výsledku algoritmu prohledávání do šířky , ale navíc jsou řádky a sloupce matice sousedství seřazeny v lexikografickém pořadí .

Aplikace

Lexikografický algoritmus prohledávání do šířky se používá k rozpoznání akordických grafů , přičemž obarví zcela oddělitelné grafy . K rozpoznání jednotlivých intervalů a intervalových grafů se používají víceskokové algoritmy (několikrát je použit lexikografický algoritmus prohledávání do šířky s variacemi).

Poznámky

1. ↑ Corneil (2004) .

Literatura

• Brandstädt, Andreas ; Le, Van Bang & Spinrad, Jeremy (1999), Graph Classes: A Survey , Monografie SIAM o diskrétní matematice a aplikacích, ISBN 0-89871-432-X  .
• Bretscher, Anna; Corneil, Derek ; Habib, Michel & Paul, Christophe (2008), A simple linear time LexBFS cograph recognition algorithm , SIAM Journal on Discrete Mathematics vol . 22(4): 1277–1296, doi : 10.1137/060664690 , < http://www.liafa .jussieu.fr/~habib/Documents/cograph.ps >  .
• Corneil, Derek G. (2004), Lexicographic width first search – an survey , Graph-Theoretic Methods in Computer Science: 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers , vol. 3353, Poznámky k přednáškám z informatiky, Springer-Verlag, s. 1–19 , DOI 10.1007/978-3-540-30559-0_1  .
• Habib, Michel; McConnell, Ross; Paul, Christophe & Viennot, Laurent (2000), Lex-BFS a zpřesňování oddílů s aplikacemi pro tranzitivní orientaci, rozpoznávání intervalových grafů a následné testování , Theoretical Computer Science vol. 234 (1–2): 59–84, doi : 10.1016/S0304-3975(97)00241-7 , < http://www.cecm.sfu.ca/~cchauve/MATH445/PROJECTS/MATH445-TCS-234-59.pdf > . Získáno 7. června 2016. Archivováno 26. července 2011 na Wayback Machine . 
• Rose, DJ; Tarjan, RE & Lueker, GS (1976), Algorithmické aspekty eliminace vrcholů na grafech , SIAM Journal on Computing , svazek 5 (2): 266–283 , DOI 10.1137/0205021  .