| dbo:abstract
|
- In graph theory, a quotient graph Q of a graph G is a graph whose vertices are blocks of a partition of the vertices of G and where block B is adjacent to block C if some vertex in B is adjacent to some vertex in C with respect to the edge set of G. In other words, if G has edge set E and vertex set V and R is the equivalence relation induced by the partition, then the quotient graph has vertex set V/R and edge set {([u]R, [v]R) | (u, v) ∈ E(G)}. More formally, a quotient graph is a quotient object in the category of graphs. The category of graphs is concretizable – mapping a graph to its set of vertices makes it a concrete category – so its objects can be regarded as "sets with additional structure", and a quotient graph corresponds to the graph induced on the quotient set V/R of its vertex set V. Further, there is a graph homomorphism (a quotient map) from a graph to a quotient graph, sending each vertex or edge to the equivalence class that it belongs to. Intuitively, this corresponds to "gluing together" (formally, "identifying") vertices and edges of the graph. (en)
- Факторграф Q графа G — граф, вершины которого являются блоками разбиения вершин графа G, а блок B смежен блоку C, если некоторая вершина в B смежна некоторой вершине в C. Другими словами, если G имеет набор рёбер E и набор вершин V и R является отношением эквивалентности, порождённым разбиением, то факторграф имеет набор вершин V/R и набор рёбер . Более формально, факторграф — это факторобъект в категории графов. Категория графов конкретизируема — отображение графа в его множество вершин делает его конкретной категорией, так что его объекты можно рассматривать как «множества с дополнительной структурой», а факторграф соответствует графу, порождённому на фактормножестве V/R его множеством вершин V. Далее имеется гомоморфизм графов (факторотображение) из графа в факторграф, переводящее каждую вершину или ребро в класс эквивалентности, которому он принадлежит. Интуитивно, это соответствует «склеиванию» (формально, «отождествлению») вершин и рёбер графа. (ru)
|
| rdfs:comment
|
- In graph theory, a quotient graph Q of a graph G is a graph whose vertices are blocks of a partition of the vertices of G and where block B is adjacent to block C if some vertex in B is adjacent to some vertex in C with respect to the edge set of G. In other words, if G has edge set E and vertex set V and R is the equivalence relation induced by the partition, then the quotient graph has vertex set V/R and edge set {([u]R, [v]R) | (u, v) ∈ E(G)}. (en)
- Факторграф Q графа G — граф, вершины которого являются блоками разбиения вершин графа G, а блок B смежен блоку C, если некоторая вершина в B смежна некоторой вершине в C. Другими словами, если G имеет набор рёбер E и набор вершин V и R является отношением эквивалентности, порождённым разбиением, то факторграф имеет набор вершин V/R и набор рёбер . (ru)
|
