Cтраница 1
Граф многогранника М ( а, Ь) е Ш1 ( т, п, k), 2 sg / nsg; п, п э 5, с минимальным числом вершин является гамильтоновым. [1]
Интерес к исследованию метрических характеристик графа многогранника возник сравнительно недавно и вызван широким распространением методов линейного программирования. [2]
Пусть eij - число ребер графа многогранника, степени концевых вершин которого равны i и / соответственно. [3]
Пусть G - многогранник ( или граф многогранника), все грани которого ограничены пятиугольниками и шестиугольниками; что можно сказать о числе пятиугольных граней. Докажите, что если в каждой вершине сходятся в точности три грани, то число пятиугольных граней должно равняться двенадцати. [4]
Определение 2.7. Толщина многогранника М ( обозначается определяется как число вершин в самой длинной простой цепи графа многогранника. [5]
На основании теоремы 1.1 достаточно показать, что удаление любых d - l вершин не нарушает связность графа многогранника. [6]
Если 93i не имеет внешних вершин помимо тех, что содержит F, то удаление таких вершин делает граф многогранника М не связным, что невозможно по условию. [7]
Тогда W ( C) Mans, а многогранники W ( L), W ( К) есть допустимая область соответственно в задаче о линейном размещении графа и в задаче о разрезании графа. Граф многогранника W ( R) является полным. [8]
Если в графе G ( M) имеется простой остовный цикл С, то G называется гамильтоновым графом, а С - гамильтоновым циклом. Таким образом, если граф многогранника М - гамильтонов, то толщина Я ( / И) равна числу вершин многогранника. [9]
Тейт построил пример, показывающий, что если в кубическом графе есть мост, то граф может не быть разложимым на три совершенных паросочетания. Далее он утверждал, что если кубический граф является графом многогранника, то такое разложение всегда осуществимо. [10]
Отметим, что для каждых d и п ( n sd l) существует d - мно-гогранник с п вершинами, граф которого гамильтонов. Для d3 каждый циклический d - многогранник 2-смежно-стный ( это означает, что любые две вершины соединены ребром) и, следовательно, его граф гамильтонов. Для d 3, воспользовавшись характеризацией 1-граней, легко показать, что граф многогранника С ( 3, п) также гамильтонов. Она достигается на симплициальных многогранниках. [11]