| dbo:abstract
|
- In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an (r, g)-graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. An (r, g)-cage is an (r, g)-graph with the smallest possible number of vertices, among all (r, g)-graphs. A (3, g)-cage is often called a g-cage. It is known that an (r, g)-graph exists for any combination of r ≥ 2 and g ≥ 3. It follows that all (r, g)-cages exist. If a Moore graph exists with degree r and girth g, it must be a cage. Moreover, the bounds on the sizes of Moore graphs generalize to cages: any cage with odd girth g must have at least vertices, and any cage with even girth g must have at least vertices. Any (r, g)-graph with exactly this many vertices is by definition a Moore graph and therefore automatically a cage. There may exist multiple cages for a given combination of r and g. For instance there are three nonisomorphic (3, 10)-cages, each with 70 vertices: the Balaban 10-cage, the Harries graph and the Harries–Wong graph. But there is only one (3, 11)-cage: the Balaban 11-cage (with 112 vertices). (en)
- En el área matemática de la teoría de grafos, una jaula es un grafo regular que tiene la menor cantidad de vértices posible para su cintura. Formalmente, un (r,g)-grafo se define como un grafo en el cual cada vértice tiene exactamente r vecinos, y en el cual el ciclo más corto tiene una longitud exactamente de g. Se sabe que existen (r,g)-grafos para cualquier combinación de r ≥ 2 y g ≥ 3. Una (r,g)-jaula es un (r,g)-grafo con el menor número de vértices posible, entre todos los (r,g)-grafos. Si existe un de grado r y cintura g, debe ser una jaula. Es más, los límites de los tamaños de los grafos de Moore se generalizan a las jaulas: cualquier jaula de cintura impar g debe tener como mínimo vértices, y cualquier jaula de cintura par g debe tener como mínimo vértices. Cualquier (r,g)-grafo con exactamente esta cantidad de vértices es por definición un grafo de Moore y por lo tanto automáticamente una jaula. Pueden existir varias jaulas para una combinación dada de r y g. Por ejemplo, hay tres (3,10)-jaulas no isomórficas, cada una con 70 vértices : la 10-jaula de Balaban, el y el . Pero existe solo una (3,11)-jaula : la (con 112 vértices). (es)
- グラフ理論において、ケージとは与えられた与えられた内周を満たす正則グラフのうち、頂点数が最小のものである。 厳密に述べると次のようになる。(r,g)-グラフとは任意の頂点が相異なるr個の頂点と隣接し、かつグラフに含まれる最小のサイクルの長さがgに一致するものを指す。任意のr ≥ 2、g ≥ 3に対して(r,g)-グラフは存在することが知られている。(r,g)-ケージとは(r,g)-グラフのうちもっとも頂点数が少ないグラフのことである。 次数r、内周gのムーアグラフは存在すれば、ケージとなる。ムーアグラフの頂点数を表す式はケージに対して一般化することができる。すなわち奇内周gをもつグラフの頂点数は 以上となる。任意の(r,g)-グラフが上述の式を満たすと、定義からムーアグラフとなり、またケージとなる。同様に偶内周の場合は頂点数は 以上となる。またrとgの組み合わせによっては複数の同型でないケージが存在しうる。例えば、頂点数70となる(3,10)-ケージは、との同型でない三つが存在する。一方で (3,11)-ケージは頂点数が112となるのみである。 (ja)
- En théorie des graphes, une cage est un graphe régulier minimal pour une maille donnée. Plus précisément, une (r,g)-cage est un graphe régulier minimal de degré r et de maille g. Quand le terme de g-cage est employé, il s'agit en fait d'une cage cubique, c'est-à-dire d'une (3,g)-cage. (fr)
- n-клетка — кубический граф обхвата n с наименьшим возможным числом вершин. Граф называется кубическим, если из каждой его вершины выходят 3 ребра. Обхват графа — это длина наименьшего цикла в нём. Для каждого 2 < n < 9 существует единственная n-клетка, причем все эти графы обладают высокой симметрией (являются унитранзитивными). Кроме того, при изображении на плоскости они часто дают экстремальное количество самопересечений, далее .
* 3-клетка — К4, остов тетраэдра, 4 вершины.
* 4-клетка — К3,3, один из двух минимальных не планарных графов, 6 вершин.
* 5-клетка — Граф Петерсена, 10 вершин. Минимальный кубический граф с индексом самопересечения 2.
* 6-клетка — Граф Хивуда, 14 вершин. Разбивается на 1-факторы (то есть, реберно раскрашиваем), любая сумма двух факторов образует гамильтонов цикл. Минимальный кубический граф с индексом самопересечения 3.
* 7-клетка — Граф МакГи, 24 вершины. Минимальный кубический граф с индексом самопересечения 8.
* 8-клетка — Граф Татта — Коксетера, 30 вершин. (ru)
- n-клітка — кубічний граф обхвату n з найменшим можливим числом вершин. Граф називається кубічним, якщо з кожної його вершини виходять 3 ребра. Обхват графа — це довжина найменшого циклу в ньому.
* 3-клітка — К4, остов тетраедра, 4 вершини.
* 4-клітка — К3,3, один з двох мінімальних не планарних графів, 6 вершин.
* 5-клітка — граф Петерсена, 10 вершин. Мінімальний кубічний граф з індексом самоперетину 2.
* 6-клітка — граф Хівуда, 14 вершин. Розбивається на 1-фактори (тобто, реберно розфарбовуємий), будь-яка сума двох чинників утворює гамільтонів цикл. Мінімальний кубічний граф з індексом самоперетину 3.
* 7-клітка — граф Маꥳ, 24 вершини. Мінімальний кубічний граф з індексом самоперетину 8.
* 8-клітка — граф Татта — Коксетера, 30 вершин. (uk)
|
| rdfs:comment
|
- グラフ理論において、ケージとは与えられた与えられた内周を満たす正則グラフのうち、頂点数が最小のものである。 厳密に述べると次のようになる。(r,g)-グラフとは任意の頂点が相異なるr個の頂点と隣接し、かつグラフに含まれる最小のサイクルの長さがgに一致するものを指す。任意のr ≥ 2、g ≥ 3に対して(r,g)-グラフは存在することが知られている。(r,g)-ケージとは(r,g)-グラフのうちもっとも頂点数が少ないグラフのことである。 次数r、内周gのムーアグラフは存在すれば、ケージとなる。ムーアグラフの頂点数を表す式はケージに対して一般化することができる。すなわち奇内周gをもつグラフの頂点数は 以上となる。任意の(r,g)-グラフが上述の式を満たすと、定義からムーアグラフとなり、またケージとなる。同様に偶内周の場合は頂点数は 以上となる。またrとgの組み合わせによっては複数の同型でないケージが存在しうる。例えば、頂点数70となる(3,10)-ケージは、との同型でない三つが存在する。一方で (3,11)-ケージは頂点数が112となるのみである。 (ja)
- En théorie des graphes, une cage est un graphe régulier minimal pour une maille donnée. Plus précisément, une (r,g)-cage est un graphe régulier minimal de degré r et de maille g. Quand le terme de g-cage est employé, il s'agit en fait d'une cage cubique, c'est-à-dire d'une (3,g)-cage. (fr)
- n-клітка — кубічний граф обхвату n з найменшим можливим числом вершин. Граф називається кубічним, якщо з кожної його вершини виходять 3 ребра. Обхват графа — це довжина найменшого циклу в ньому.
* 3-клітка — К4, остов тетраедра, 4 вершини.
* 4-клітка — К3,3, один з двох мінімальних не планарних графів, 6 вершин.
* 5-клітка — граф Петерсена, 10 вершин. Мінімальний кубічний граф з індексом самоперетину 2.
* 6-клітка — граф Хівуда, 14 вершин. Розбивається на 1-фактори (тобто, реберно розфарбовуємий), будь-яка сума двох чинників утворює гамільтонів цикл. Мінімальний кубічний граф з індексом самоперетину 3.
* 7-клітка — граф Маꥳ, 24 вершини. Мінімальний кубічний граф з індексом самоперетину 8.
* 8-клітка — граф Татта — Коксетера, 30 вершин. (uk)
- In the mathematical area of graph theory, a cage is a regular graph that has as few vertices as possible for its girth. Formally, an (r, g)-graph is defined to be a graph in which each vertex has exactly r neighbors, and in which the shortest cycle has length exactly g. An (r, g)-cage is an (r, g)-graph with the smallest possible number of vertices, among all (r, g)-graphs. A (3, g)-cage is often called a g-cage. It is known that an (r, g)-graph exists for any combination of r ≥ 2 and g ≥ 3. It follows that all (r, g)-cages exist. vertices, and any cage with even girth g must have at least (en)
- En el área matemática de la teoría de grafos, una jaula es un grafo regular que tiene la menor cantidad de vértices posible para su cintura. Formalmente, un (r,g)-grafo se define como un grafo en el cual cada vértice tiene exactamente r vecinos, y en el cual el ciclo más corto tiene una longitud exactamente de g. Se sabe que existen (r,g)-grafos para cualquier combinación de r ≥ 2 y g ≥ 3. Una (r,g)-jaula es un (r,g)-grafo con el menor número de vértices posible, entre todos los (r,g)-grafos. vértices, y cualquier jaula de cintura par g debe tener como mínimo (es)
- n-клетка — кубический граф обхвата n с наименьшим возможным числом вершин. Граф называется кубическим, если из каждой его вершины выходят 3 ребра. Обхват графа — это длина наименьшего цикла в нём. Для каждого 2 < n < 9 существует единственная n-клетка, причем все эти графы обладают высокой симметрией (являются унитранзитивными). Кроме того, при изображении на плоскости они часто дают экстремальное количество самопересечений, далее . (ru)
|
