In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Cajeidad (es)
- Boxicity (en)
- Интервальная размерность графа (ru)
- Інтервальна розмірність графа (uk)
|
| rdfs:comment
| - In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices. (en)
- En teoría de grafos, la cajeidad (boxicity en inglés) es un , introducido por en 1969. La cajeidad de un grafo es la dimensión mínima en la que un grafo dado puede representarse como un grafo de intersección de cajas paralelas a un sistema de ejes. Es decir, debe existir una correspondencia biunívoca entre los vértices del grafo y un conjunto de cajas, tal que dos cajas se intersecan si y solo si hay una arista en el grafo que conecta los vértices correspondientes. (es)
- В теории графов интервальная размерность графа — это инвариант графа, введённый Фредом С. Робертсом в 1969. Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины. (ru)
- У теорії графів інтервальна розмірність графа — це інваріант графа, введений Фредом С. Робертсом у 1969 році. Інтервальна розмірність графа — це мінімальна розмірність, в якій заданий граф можна подати у вигляді графа перетинів гіперпрямокутників (тобто багатовимірних прямокутних паралелепіпедів) з паралельними осям ребрами. Тобто має існувати відповідність один-до-одного між вершинами графа та множиною гіперпрямокутників, таких, що прямокутники перетинаються тоді й лише тоді, коли існує ребро, яке з'єднує відповідні вершини. (uk)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969. The boxicity of a graph is the minimum dimension in which a given graph can be represented as an intersection graph of axis-parallel boxes. That is, there must exist a one-to-one correspondence between the vertices of the graph and a set of boxes, such that two boxes intersect if and only if there is an edge connecting the corresponding vertices. (en)
- En teoría de grafos, la cajeidad (boxicity en inglés) es un , introducido por en 1969. La cajeidad de un grafo es la dimensión mínima en la que un grafo dado puede representarse como un grafo de intersección de cajas paralelas a un sistema de ejes. Es decir, debe existir una correspondencia biunívoca entre los vértices del grafo y un conjunto de cajas, tal que dos cajas se intersecan si y solo si hay una arista en el grafo que conecta los vértices correspondientes. (es)
- В теории графов интервальная размерность графа — это инвариант графа, введённый Фредом С. Робертсом в 1969. Интервальная размерность графа — это минимальная размерность, в которой заданный граф может быть представлен в виде графа пересечений гиперпрямоугольников (то есть многомерных прямоугольных параллелепипедов) с параллельными осям рёбрами. То есть должно существовать один-к-одному соответствие между вершинами графа и множеством гиперпрямоугольников, таких, что прямоугольники пересекаются тогда и только тогда, когда существует ребро, соединяющее соответствующие вершины. (ru)
- У теорії графів інтервальна розмірність графа — це інваріант графа, введений Фредом С. Робертсом у 1969 році. Інтервальна розмірність графа — це мінімальна розмірність, в якій заданий граф можна подати у вигляді графа перетинів гіперпрямокутників (тобто багатовимірних прямокутних паралелепіпедів) з паралельними осям ребрами. Тобто має існувати відповідність один-до-одного між вершинами графа та множиною гіперпрямокутників, таких, що прямокутники перетинаються тоді й лише тоді, коли існує ребро, яке з'єднує відповідні вершини. (uk)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
