Простой граф

Cтраница 1

Простой граф, требующий [ 3 / 2 / п ] цветов, может быть построен следующим образом. Для т 2п пусть каждая пара из трех вершин А, В, С соединена п ребрами. [1]

Примеры графов. [2]

Простой граф определяется также отношением смежности а на V: рщ означает, что вершины р и q соединены ( единственным) ребром. Отношение иррефлексивно и симметрично. [3]

Полные неориентированные графы.| Исходный граф Г и дополнительный Г.| Граф Г - плоский, а граф Г2 - неплоский. [4]

Простой граф называется полным, если каждая пара вершин соединена ребром. [5]

Простой граф определяется как пара G ( V. [6]

Простой граф, в котором любые две вершины смежны, называется полным графом. [7]

Простой граф, изоморфный своему дополнению, называется самодополнительным. Докажите, что число вершин самодополнительного графа представимо в виде 4fe или 4fe 1, где k - целое, и найдите все самодополнительные графы с четырьмя и пятью вершинами. [8]

Пусть простой граф G содержит не менее одиннадцати вершин, и пусть G - его дополнение; покажите, что G и G не могут оба быть пленарными. На самом деле такой же результат можно доказать для девяти вершин вместо одиннадцати. Приведите пример графа G с восемью вершинами, обладающего тем свойством, что оба графа G и G планарны. [9]

Образовав простой граф инциденций вершины - ребра, получим, что вершина vp образует р / 2 ребер графа. [10]

Образовав простой граф инциденций вершины - грани, получим, что вершина v p образует р / т ] внутренних граней графа, так как эта вершина инцидентна р граням, а каждая внутренняя грань инцидентна ц вершинам. [11]

Паросочетанием простого графа называется набор дуг, все начала и все концы которых различны Естественно возникает задача о выборе наибольшего такого набора. [12]

Двудольным называется простой граф, множество вершин X которого распадается на две грушш X и X, состоящие соответственно из п и т вершин, таких, что ребра связывают только те вершины, которые не принадлежат одной и той же группе. Каждой прямоугольной матрице А размера п т может быть поставлен в соответствие двудольный граф, такой, что ребро в связывает вершину х а из части Xi с вершиной хД из части Л2 только тогда. [13]

Если задан произвольный простой граф, то в общем случае трудно получить его хроматическую функцию чисто умозрительным путем. [14]

Хроматическая функция простого графа представляет сдбой многочлен. [15]

Страницы: 1 2 3 4