| dbo:abstract
|
- 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 legnagyobb csúcshalmazával, a gráf merev körű kiegészítésében található legnagyobb klikkel, a gráfon játszott elkerülési stratégiáját leíró vagy az egymást kölcsönösen érintő összefüggő részgráfok, azaz -ök maximális rendjével. A faszélesség gyakran előkerül gráfalgoritmusok vizsgálatakor. A legfeljebb k faszélességű gráfokat 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 -nél jelent meg „dimenzió” név alatt. Később fedezte fel újra, a Hadwiger-számmal közös tulajdonságai alapján. Majd and ismét felfedezték, és azóta számos más szerző is tanulmányozta. (hu)
- 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 legnagyobb csúcshalmazával, a gráf merev körű kiegészítésében található legnagyobb klikkel, a gráfon játszott elkerülési stratégiáját leíró vagy az egymást kölcsönösen érintő összefüggő részgráfok, azaz -ök maximális rendjével. A faszélesség gyakran előkerül gráfalgoritmusok vizsgálatakor. A legfeljebb k faszélességű gráfokat 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 -nél jelent meg „dimenzió” név alatt. Később fedezte fel újra, a Hadwiger-számmal közös tulajdonságai alapján. Majd and ismét felfedezték, és azóta számos más szerző is tanulmányozta. (hu)
|
