| dbo:abstract
|
- In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem. Similarly, an induced cycle is a cycle that is an induced subgraph of G; induced cycles are also called chordless cycles or (when the length of the cycle is four or more) holes. An antihole is a hole in the complement of G, i.e., an antihole is a complement of a hole. The length of the longest induced path in a graph has sometimes been called the detour number of the graph; for sparse graphs, having bounded detour number is equivalent to having bounded tree-depth. The induced path number of a graph G is the smallest number of induced paths into which the vertices of the graph may be partitioned, and the closely related path cover number of G is the smallest number of induced paths that together include all vertices of G. The girth of a graph is the length of its shortest cycle, but this cycle must be an induced cycle as any chord could be used to produce a shorter cycle; for similar reasons the odd girth of a graph is also the length of its shortest odd induced cycle. (en)
- 無向グラフG中の誘導パスは， Gの誘導グラフかつ道であるグラフのことである．つまり，誘導パスはそのパス上で隣接している任意の頂点対はG中で隣接しており，かつ，隣接していない任意の頂点対はG中で隣接していないような，G中の頂点の列である．誘導パスは，スネークとも呼ばれ，超立方体上の最長誘導パスを発見する問題は，en:Snake-in-the-box問題として知られている． また，誘導サイクルは，en:閉路をなすGの誘導グラフのことである．また，誘導サイクルは，コードレスサイクルや，その長さが4以上のとき，ホールとも呼ばれる．アンチホールは，Gの補グラフにおけるホールである． グラフ中の最長誘導パスの長さは，そのグラフのう回路数と呼ばれる． 任意のen:疎グラフに対して，う回路数が固定された時は，w:tree-depthが固定されている時と等価である． グラフGの誘導パス数とは，グラフを分割するのに必要な最小の誘導パスの数である． また，Gのパス被覆は，Gのすべての頂点を覆うために必要な誘導パスの最小数である． グラフGの内周は，G中の最小のサイクルの長さであるが，そのサイクルは，誘導サイクルである．同様に，奇内周は，グラフにおける奇数長の最短な誘導サイクルの長さのことである． (ja)
- В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G. Порождённый путь иногда называют змеёй и задача поиска самого длинного порождённого пути в графах гиперкубов известна как задача о змее в коробке. Также порождённым циклом называется цикл, являющийся порождённым подграфом G. Порождённые циклы называются также циклами без хорд или (если длина цикла не меньше четырёх) дырами. Антидыра — это дыра в дополнении графа G, то есть антидыра — это дополнение дыры. Длину наибольшего порождённого пути в графе иногда называют числом обхода графа. Для разреженных графов существование ограниченного числа обхода эквивалентно существованию ограниченной глубины дерева. Порождённым числом обхода графа G называется наименьшее число подмножеств вершин, на которые можно разложить вершины графа, чтобы каждое подмножество образовывало порождённый путь, и это понятие тесно связано с числом покрытия путями — минимальное число несвязных путей, являющихся порождёнными подграфами G, покрывающих все вершины G. Обхват графа — это длина его кратчайшего цикла, но этот цикл должен быть порождённым циклом, так как любая хорда могла бы образовать более короткий цикл. По тем же причинам нечётным обхватом графа называется длина его кратчайшего нечётного порождённого цикла. (ru)
- В теорії графів породженим шляхом в неорієнтованому графі G називається шлях, що є породженим підграфом G. Таким чином, це послідовність вершин в G, така, що будь-які дві суміжні вершини в послідовності з'єднані ребром в G і будь-які дві несуміжні вершини послідовності не з'єднані ребром G. Породжений шлях іноді називають змією і завдання пошуку найдовшого породженого шляху в графах гіперкубів відоме як задача про змію в коробці.Таким же чином, породженим циклом називається цикл, що є породженим підграфом G. Породжені цикли називаються також циклами без хорд або (якщо довжина циклу не менше чотирьох) дірками. Антидіра — це діра в доповненні графу G, тобто антидіра — це доповнення діри. Довжину найбільшого породженого шляху в графі іноді називають числом обходу графу. Для розріджених графів існування обмеженого числа обходу еквівалентно існуванню обмеженої глибини дерева. Породженим числом обходу графу G називається найменше число підмножин вершин, на які можна розкласти вершини графу, щоб кожна підмножина утворювала породжений шлях, і це поняття тісно пов'язане з числом покриття шляхами — мінімальне число незв'язних шляхів, що є породженими підграфами G, які покривають всі вершини G. Обхват графу — це довжина його найкоротшого циклу, але цей цикл повинен бути породженим циклом, оскільки будь-яка хорда могла б утворити більш короткий цикл. З тих же причин непарним обхватом графу називається довжина його найкоротшого непарного породженого циклу. (uk)
|
| rdfs:comment
|
- 無向グラフG中の誘導パスは， Gの誘導グラフかつ道であるグラフのことである．つまり，誘導パスはそのパス上で隣接している任意の頂点対はG中で隣接しており，かつ，隣接していない任意の頂点対はG中で隣接していないような，G中の頂点の列である．誘導パスは，スネークとも呼ばれ，超立方体上の最長誘導パスを発見する問題は，en:Snake-in-the-box問題として知られている． また，誘導サイクルは，en:閉路をなすGの誘導グラフのことである．また，誘導サイクルは，コードレスサイクルや，その長さが4以上のとき，ホールとも呼ばれる．アンチホールは，Gの補グラフにおけるホールである． グラフ中の最長誘導パスの長さは，そのグラフのう回路数と呼ばれる． 任意のen:疎グラフに対して，う回路数が固定された時は，w:tree-depthが固定されている時と等価である． グラフGの誘導パス数とは，グラフを分割するのに必要な最小の誘導パスの数である． また，Gのパス被覆は，Gのすべての頂点を覆うために必要な誘導パスの最小数である． グラフGの内周は，G中の最小のサイクルの長さであるが，そのサイクルは，誘導サイクルである．同様に，奇内周は，グラフにおける奇数長の最短な誘導サイクルの長さのことである． (ja)
- In the mathematical area of graph theory, an induced path in an undirected graph G is a path that is an induced subgraph of G. That is, it is a sequence of vertices in G such that each two adjacent vertices in the sequence are connected by an edge in G, and each two nonadjacent vertices in the sequence are not connected by any edge in G. An induced path is sometimes called a snake, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem. (en)
- В теории графов порождённым путём в неориентированном графе G называется путь, являющийся порождённым подграфом G. Таким образом, это последовательность вершин в G такая, что любые две смежные вершины в последовательности соединены ребром в G, и любые две несмежные вершины последовательности не соединены ребром G. Порождённый путь иногда называют змеёй и задача поиска самого длинного порождённого пути в графах гиперкубов известна как задача о змее в коробке. (ru)
- В теорії графів породженим шляхом в неорієнтованому графі G називається шлях, що є породженим підграфом G. Таким чином, це послідовність вершин в G, така, що будь-які дві суміжні вершини в послідовності з'єднані ребром в G і будь-які дві несуміжні вершини послідовності не з'єднані ребром G. Породжений шлях іноді називають змією і завдання пошуку найдовшого породженого шляху в графах гіперкубів відоме як задача про змію в коробці.Таким же чином, породженим циклом називається цикл, що є породженим підграфом G. Породжені цикли називаються також циклами без хорд або (якщо довжина циклу не менше чотирьох) дірками. Антидіра — це діра в доповненні графу G, тобто антидіра — це доповнення діри. (uk)
|
