Полный двудольный граф
Cтраница 1
Полный двудольный граф / С ( т, п) состоит из m темных точек, п светлых и тп линий, соединяющих точки разных типов. [1]
 |
Остовные подграфы некоторого графа. [2] |
Полный двудольный граф Кт имеет т п вершин, из которых т окрашены в один цвет, an - в другой, и две вершины смежны тогда и только тогда, когда они окрашены в разные цвета. [3]
 |
Остовные подграфы некоторого графа. [4] |
Полный двудольный граф Кт имеет т п вершин, из которых т окрашены в один цвет, а га - в другой, и две вершины смежны тогда и только тогда, когда они окрашены в разные цвета. [5]
Рассматривая полный двудольный граф, , легко видеть, что задача о паросочетании для этого специального случая может быть решена с помощью методов, предназначенных для исследования потоков в сетях ( из гл. Очевидно, что в случае такой специальной структуры графа многие шаги общего алгоритма нахождения потока минимальной стоимости ( веса) могут быть упрощены с целью получения более эффективной процедуры для ЗН. [6]
Рассматривая полный двудольный граф Кп, п, легко видеть, что задача о паросочетании для этого специального случая может быть решена с помощью методов, предназначенных для исследования потоков в сетях ( из гл. Очевидно, что в случае такой специальной структуры графа многие шаги общего алгоритма нахождения потока минимальной стоимости ( веса) могут быть упрощены с целью получения более эффективной процедуры для ЗН. [7]
Для полных двудольных графов соответствующий результат, менее трудоемкий, получил Рингель. [8]
Для полных двудольных графов известна формула К. [9]
 |
Минимальное разложение графа К, на остовные леса. [10] |
Древесности полных и полных двудольных графов равны Т ( КР) р / 2 и Т ( Kr s) rs / ( r s - 1) соответственно. [11]
 |
Предполагаемые значения для ( Кр. [12] |
Для крупности полных двудольных графов результаты Гая и Байнеке [2] не полны; они включают много случаев. [13]
 |
Контрпример к гипотезе.| Реберно-регулярный ребер - Теперь Сформулируем теоре. [14] |
На рис. 14.10 показан полный двудольный граф Л 2 з; он реберно-симметричен, реберно-регулярен степени ( 2 3), но не является вершинно-симметрическим. [15]
Страницы: 1 2 3 4