Faszélesség
gráfelméleti fogalom / From Wikipedia, the free encyclopedia
A matematika, azon belül a gráfelmélet területén egy irányítatlan gráf faszélessége vagy favastagsága (treewidth) egy a gráf szerkezetétől függő, a gráfhoz rendelt szám, azaz gráftulajdonság. A faszélesség több, egymással egyenértékű módon definiálható: a gráf fafelbontása legnagyobb csúcshalmazával, a gráf merev körű kiegészítésében található legnagyobb klikkel, a gráfon játszott üldözős-menekülős játék elkerülési stratégiáját leíró menedékkel vagy az egymást kölcsönösen érintő összefüggő részgráfok, azaz bramble-ök maximális rendjével.
A faszélesség gyakran előkerül gráfalgoritmusok parametrikus bonyolultságának vizsgálatakor. A legfeljebb k faszélességű gráfokat részleges k-fáknak is nevezik; számos, részletekbe menően tanulmányozott gráfcsalád rendelkezik korlátozott faszélességgel.
A faszélesség koncepciója először Umberto Bertelé and Francesco Brioschi (1972)-nél jelent meg „dimenzió” név alatt. Később Rudolf Halin (1976) fedezte fel újra, a Hadwiger-számmal közös tulajdonságai alapján. Majd Neil Robertson and Paul Seymour (1984) ismét felfedezték, és azóta számos más szerző is tanulmányozta.[1]