Уравновешенные 2D-разбиения графов

• Published in: Компьютерная математика
• Date: 2011
• Main Authors: Провотар, Т.М., Протасова, К.Д.
• Format: Article
• Language: Russian
• Published: Інститут кібернетики ім. В.М. Глушкова НАН України 2011
• Subjects: Теория и методы оптимизации
• Online Access: https://nasplib.isofts.kiev.ua/handle/123456789/84617
• Journal Title: Digital Library of Periodicals of National Academy of Sciences of Ukraine
• Cite this: Уравновешенные 2D-разбиения графов / Т.М. Провотар, К.Д. Протасова // Компьютерная математика: сб. науч. тр. — 2011. — № 1. — С. 150-156. — Бібліогр.: 3 назв. — рос.

Показано, что для произвольного конечного связного графа с множеством вершин V существует уравновешенное разбиение V=V1 U V2 такое, что ind V1=1, ind V2=2. Рассмотрено и исследовано также два игровых варианта этого утверждения. Показано, що для довільного скінченного зв’язного графа з множиною верши...