Oriented coloring (original) (raw)
Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа, которое * правильное — никакие две смежные вершины не получают один и тот же цвет, * сохраняется ориентация — если (x, y) и (u, v) являются дугами в графе, то недопустимо, чтобы цвета вершин x и v, а также цвета вершин y и u совпадали. Другое определение: Ориентированная k-раскраска орграфа H есть ориентированный гомоморфизм в k-вершинный орграф H*.
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, oriented graph coloring is a special type of graph coloring. Namely, it isan assignment of colors to vertices of an oriented graph that * is proper: no two adjacent vertices get the same color, and * is consistently oriented: if vertices and have the same color, and vertices and have the same color, then and cannot both be edges in the graph. Equivalently, an oriented graph coloring of a graph G is an oriented graph H (whose vertices represent colors and whose arcs represent valid orientations between colors) such that there exists a homomorphism from G to H. An oriented chromatic number of a graph G is the fewest colors needed in an oriented coloring;it is usually denoted by . The same definition can be extended to undirected graphs, as well, by defining the oriented chromatic number of an undirected graph to be the largest oriented chromatic number of any of its orientations. (en) Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа, которое * правильное — никакие две смежные вершины не получают один и тот же цвет, * сохраняется ориентация — если (x, y) и (u, v) являются дугами в графе, то недопустимо, чтобы цвета вершин x и v, а также цвета вершин y и u совпадали. Другое определение: Ориентированная k-раскраска орграфа H есть ориентированный гомоморфизм в k-вершинный орграф H*. (ru) |
| dbo:wikiPageExternalLink | http://www.labri.fr/perso/sopena/pmwiki/index.php%3Fn=TheOrientedColoringPage.TheOrientedColoringPage |
| dbo:wikiPageID | 12606685 (xsd:integer) |
| dbo:wikiPageLength | 4105 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 950979891 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Degree_(graph_theory) dbc:Graph_coloring dbr:Complete_coloring dbr:Orientation_(graph_theory) dbr:Graph_coloring dbr:Graph_homomorphism dbr:Acyclic_coloring dbr:Tournament_(graph_theory) dbr:Graph_embedding dbr:Graph_theory dbr:Oriented_graph |
| dbp:wikiPageUsesTemplate | dbt:Reflist |
| dcterms:subject | dbc:Graph_coloring |
| rdfs:comment | Ориентированная раскраска графа — это специальный вид раскраски графов. А именно, это назначение цветов вершинам ориентированного графа, которое * правильное — никакие две смежные вершины не получают один и тот же цвет, * сохраняется ориентация — если (x, y) и (u, v) являются дугами в графе, то недопустимо, чтобы цвета вершин x и v, а также цвета вершин y и u совпадали. Другое определение: Ориентированная k-раскраска орграфа H есть ориентированный гомоморфизм в k-вершинный орграф H*. (ru) In graph theory, oriented graph coloring is a special type of graph coloring. Namely, it isan assignment of colors to vertices of an oriented graph that * is proper: no two adjacent vertices get the same color, and * is consistently oriented: if vertices and have the same color, and vertices and have the same color, then and cannot both be edges in the graph. Equivalently, an oriented graph coloring of a graph G is an oriented graph H (whose vertices represent colors and whose arcs represent valid orientations between colors) such that there exists a homomorphism from G to H. (en) |
| rdfs:label | Oriented coloring (en) Ориентированная раскраска графа (ru) |
| owl:sameAs | freebase:Oriented coloring wikidata:Oriented coloring dbpedia-ru:Oriented coloring https://global.dbpedia.org/id/4sYXw |
| prov:wasDerivedFrom | wikipedia-en:Oriented_coloring?oldid=950979891&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Oriented_coloring |
| is dbo:wikiPageWikiLink of | dbr:Graph_coloring dbr:Graph_homomorphism |
| is foaf:primaryTopic of | wikipedia-en:Oriented_coloring |