Дерево Сюонг

В теории графов дерево Сюонга является остовным деревом. $T$ данного графа $G$ со свойством, что в оставшемся графе $G-T$ , количество компонент связности с нечетным числом ребер минимально возможно. ^[1]Они названы в честь Нгуена Хуй Сюонга, который использовал их для характеристики клеточных вложений данного графа, имеющего максимально возможный род . ^[2]

Согласно результатам Сюонга, если $T$ это дерево Сюонги числа ребер в компонентах $G-T$ являются $m_{1},m_{2},\dots ,m_{k}$ , то максимальный род вложения $G$ является $\textstyle \sum _{i=1}^{k}\lfloor m_{i}/2\rfloor$ . ^[1]^[2]Любой из этих компонентов, имеющий $m_{i}$ края, можно разделить на $\lfloor m_{i}/2\rfloor$ непересекающиеся по ребрам двухреберные пути, возможно, с одним дополнительным левым ребром. ^[3]Вложение максимального рода может быть получено из плоского вложения дерева Сюонга путем добавления каждого двуреберного пути к вложению таким образом, что это увеличивает род на единицу. ^[1]^[2]

Дерево Сюонга и полученное из него вложение максимального рода можно найти в любом графе за полиномиальное время путем преобразования к более общей вычислительной задаче на матроидах — проблеме четности матроидов для линейных матроидов . ^[1]^[4]

Ссылки

^ Jump up to: ^а ^б ^с ^д Бейнеке, Лоуэлл В .; Уилсон, Робин Дж. (2009), Темы топологической теории графов , Энциклопедия математики и ее приложений, том. 128, Издательство Кембриджского университета, Кембридж, с. 36, номер домена : 10.1017/CBO9781139087223 , ISBN 978-0-521-80230-7 , МР 2581536
^ Jump up to: ^а ^б ^с Сюонг, Нгуен Хай (1979), «Как определить максимальный род графа», Журнал комбинаторной теории , серия B, 26 (2): 217–225, doi : 10.1016/0095-8956(79)90058-3 , МР 0532589
^ Самнер, Дэвид П. (1974), «Графики с 1-факторами», Труды Американского математического общества , 42 (1), Американское математическое общество: 8–12, doi : 10.2307/2039666 , JSTOR 2039666 , MR 0323648
^ Ферст, Меррик Л.; Гросс, Джонатан Л.; МакГеоч, Лайл А. (1988), «Нахождение вложения графа максимального рода», Журнал ACM , 35 (3): 523–534, doi : 10.1145/44483.44485 , MR 0963159 , S2CID 17991210

[bw-1] Jump up to: ^а ^б ^с ^д Бейнеке, Лоуэлл В .; Уилсон, Робин Дж. (2009), Темы топологической теории графов , Энциклопедия математики и ее приложений, том. 128, Издательство Кембриджского университета, Кембридж, с. 36, номер домена : 10.1017/CBO9781139087223 , ISBN 978-0-521-80230-7 , МР 2581536

[x-2] Jump up to: ^а ^б ^с Сюонг, Нгуен Хай (1979), «Как определить максимальный род графа», Журнал комбинаторной теории , серия B, 26 (2): 217–225, doi : 10.1016/0095-8956(79)90058-3 , МР 0532589

[s-3] Самнер, Дэвид П. (1974), «Графики с 1-факторами», Труды Американского математического общества , 42 (1), Американское математическое общество: 8–12, doi : 10.2307/2039666 , JSTOR 2039666 , MR 0323648

[fgm-4] Ферст, Меррик Л.; Гросс, Джонатан Л.; МакГеоч, Лайл А. (1988), «Нахождение вложения графа максимального рода», Журнал ACM , 35 (3): 523–534, doi : 10.1145/44483.44485 , MR 0963159 , S2CID 17991210

[1]

[2]

[3]

[4]