Cтраница 1
Квазиполный граф квазиплотности К представляет собой граф GK F, [ /, обладающий следующим свойством, которое не выполняется ни для одного его частичного графа: хроматическое число графа GK равно К. Из определения квазиполного графа следует, что наличие на графе квазиполного графа квазиплотности К не позволяет его раскрасить в К красок. С другой стороны, отсутствие на графе квазиполных графов квазиплотности К делает его / - раскрашиваемым. Таким образом, квазиполные графы являются запрещенными фигурами раскраски вершин графа. Существует только один квазиполный граф квазиплотности два - это граф, состоящий из двух смежных вершин. Для случая К 3 квазиполными графами являются циклы нечетной длины. [1]
Примеры квазиполных графов квазиплотности четыре приведены на рис. 2.5. На рис. 2.6 показаны квазиполные графы К 5, мощность носителя которых не превосходит девяти. [2]
Для этого рассмотрим квазиполный граф GK квазиплотности К в виде Q ( p k), где р - плотность; k - порядок квазиполного графа, Kk p - квазиплотность графа Q ( p k), равная его хроматическому числу. [3]
Рассмотрим правила порождения квазиполных графов квазиплотности 4 из цикла нечетной длины С2п 1 ( я1) посредством генерации замещающих слоев с последующим построением замыкающего слоя. При этом справедливы следующие утверждения. [4]
Утверждение 2.7. В квазиполном графе квазиплотности А 3 любая вершина входит по крайней мере в ( А - 1) ( / С - 2) / 2 порожденных циклов нечетной длины. [5]
Утверждение 2.8. В квазиполном графе квазиплотности А 3 любое ребро входит но крайней мере в ( А - 2) порожденных циклов нечетной длины. [6]
Из сформулированных утверждений следует, что любой квазиполный граф квазиплотности А3 есть сочетание специального вида семейства порожденных циклов нечетной длины. [7]
Процедуры второго класса, порождающие квазиполные графы квазиплотности К из квазиполных графов квазиплотности К, разобраны ниже. [8]
Квазиполный граф квазиплотности К представляет собой граф GK F, [ /, обладающий следующим свойством, которое не выполняется ни для одного его частичного графа: хроматическое число графа GK равно К. Из определения квазиполного графа следует, что наличие на графе квазиполного графа квазиплотности К не позволяет его раскрасить в К красок. С другой стороны, отсутствие на графе квазиполных графов квазиплотности К делает его / - раскрашиваемым. Таким образом, квазиполные графы являются запрещенными фигурами раскраски вершин графа. Существует только один квазиполный граф квазиплотности два - это граф, состоящий из двух смежных вершин. Для случая К 3 квазиполными графами являются циклы нечетной длины. [9]
Решение характеризационной задачи многокомпонентной раскраски графов, рассмотренное в гл. К, всегда возможна, если граф сцепления автомата не содержит квазиполного графа квазиплотности К 1 без одного ребра. [10]
Квазиполный граф квазиплотности К представляет собой граф GK F, [ /, обладающий следующим свойством, которое не выполняется ни для одного его частичного графа: хроматическое число графа GK равно К. Из определения квазиполного графа следует, что наличие на графе квазиполного графа квазиплотности К не позволяет его раскрасить в К красок. С другой стороны, отсутствие на графе квазиполных графов квазиплотности К делает его / - раскрашиваемым. Таким образом, квазиполные графы являются запрещенными фигурами раскраски вершин графа. Существует только один квазиполный граф квазиплотности два - это граф, состоящий из двух смежных вершин. Для случая К 3 квазиполными графами являются циклы нечетной длины. [11]
Для получения условий функциональной несвязности элементов памяти автомата, реализованного в многозначном структурном алфавите, может использоваться тот же аппарат, что и при поиске параллельной декомпозиции автомата. Элементы памяти автомата функционально несвязны, если граф сцепления не содержит квазиполного графа квазиплотности А 1 без одного ребра, где А - значность логики, в которой описывается поведение автомата. [12]
Квазиполный граф квазиплотности К представляет собой граф GK F, [ /, обладающий следующим свойством, которое не выполняется ни для одного его частичного графа: хроматическое число графа GK равно К. Из определения квазиполного графа следует, что наличие на графе квазиполного графа квазиплотности К не позволяет его раскрасить в К красок. С другой стороны, отсутствие на графе квазиполных графов квазиплотности К делает его / - раскрашиваемым. Таким образом, квазиполные графы являются запрещенными фигурами раскраски вершин графа. Существует только один квазиполный граф квазиплотности два - это граф, состоящий из двух смежных вершин. Для случая К 3 квазиполными графами являются циклы нечетной длины. [13]