Circular coloring
http://dbpedia.org/resource/Circular_coloring
In graph theory, circular coloring is a kind of coloring that may be viewed as a refinement of the usual graph coloring. The circular chromatic number of a graph , denoted can be given by any of the following definitions, all of which are equivalent (for finite graphs). It is relatively easy to see that (especially using 1 or 2), but in fact . It is in this sense that we view circular chromatic number as a refinement of the usual chromatic number. Circular coloring was originally defined by , who called it "star coloring".
rdf:langString
Цикловую раскраску можно рассматривать как уточнение обычной раскраски графов. Цикловое хроматичеcкое число графа с обозначением можно определить следующими эквивалентными (для конечных графов) способами. Относительно несложно видеть, что (используя определение 1 или 2), но, фактически, . В этом смысле мы говорим, что цикловое хроматичеcкое число уточняет обычное хроматическое число. Цикловую раскраску первоначально определил Винс, который назвал её «звёздной раскраской».
rdf:langString
rdf:langString
Circular coloring
rdf:langString
Цикловая раскраска
rdf:langString
Circular complete graph
xsd:integer
19448392
xsd:integer
1037283725
rdf:langString
⌈n/k⌉
rdf:langString
n / 2
rdf:langString
n
rdf:langString
In graph theory, circular coloring is a kind of coloring that may be viewed as a refinement of the usual graph coloring. The circular chromatic number of a graph , denoted can be given by any of the following definitions, all of which are equivalent (for finite graphs). 1.
* is the infimum over all real numbers so that there exists a map from to a circle of circumference 1 with the property that any two adjacent vertices map to points at distance along this circle. 2.
* is the infimum over all rational numbers so that there exists a map from to the cyclic group with the property that adjacent vertices map to elements at distance apart. 3.
* In an oriented graph, declare the imbalance of a cycle to be divided by the minimum of the number of edges directed clockwise and the number of edges directed counterclockwise. Define the imbalance of the oriented graph to be the maximum imbalance of a cycle. Now, is the minimum imbalance of an orientation of . It is relatively easy to see that (especially using 1 or 2), but in fact . It is in this sense that we view circular chromatic number as a refinement of the usual chromatic number. Circular coloring was originally defined by , who called it "star coloring". Coloring is dual to the subject of nowhere-zero flows and indeed, circular coloring has a natural dual notion: circular flows.
rdf:langString
Цикловую раскраску можно рассматривать как уточнение обычной раскраски графов. Цикловое хроматичеcкое число графа с обозначением можно определить следующими эквивалентными (для конечных графов) способами. 1.
* равен инфимуму по всем вещественным числам таким, что существует отображение из в окружность с длиной, равной 1, при этом две смежные вершины отображаются в точки на расстоянии вдоль окружности. 2.
* равен инфимуму по рациональным числам таким, что существует отображение из в циклическую группу со свойством, что смежные вершины отображаются в элементы на расстоянии друг от друга. 3.
* В ориентированном графе определим дисбаланс цикла , как значение , делённое на меньшее из числа рёбер, направленных по часовой стрелке и числа рёбер, направленных против часовой стрелки. Определим дисбаланс ориентированного графа, как максимальный дисбаланс по всем циклам. Теперь, равен минимальному дисбалансу по всем ориентациям графа . Относительно несложно видеть, что (используя определение 1 или 2), но, фактически, . В этом смысле мы говорим, что цикловое хроматичеcкое число уточняет обычное хроматическое число. Цикловую раскраску первоначально определил Винс, который назвал её «звёздной раскраской». Цикловая раскраска двойственна субъекту нигде не нулевого потока и более того, цикловая раскраска имеет естественное двойственное понятие «циркуляционный поток».
xsd:nonNegativeInteger
5124
