| dbo:abstract
|
- Chordální graf je takový graf, který neobsahuje kružnici velikosti alespoň 4 jako indukovaný podgraf. (cs)
- In der Graphentheorie nennt man einen Graphen chordal oder trianguliert, genau dann wenn er einer der folgenden äquivalenten Bedingungen genügt:
* Jeder induzierte Kreis ist ein Dreieck. Ein Kreis ist dabei induziert, genau dann wenn zwischen seinen Knoten keine weiteren Kanten im Ursprungsgraphen existieren.
* Jeder minimale a-b-Trenner zu zwei Ecken a und b ist eine Clique.
* Jeder induzierte Teilgraph enthält eine simpliziale Ecke (Rose, 1970), also eine Ecke, deren Nachbarn eine Clique bilden.
* G ist einer Menge von Teilbäumen eines Baums (Gavril, 1974). (de)
- En grafeoterio, kordeca grafeo estas grafeo en kiu ĉiu ciklo kun pli ol kvar verticoj havas kordon, latero ne apartenanta al la ciklo sed ligas du verticojn el la ciklo. Ekvivalente, ĉiu en la grafeo estu precize 3-vertica. Oni povas ankaŭ priskribi kordecan grafeon 1.
* kiel grafeo kun perfekta forigada ordo 2.
* kiel grafeo, kies ĉiu minimuma disigilo estas plena, kaj 3.
* kiel komunaĵo inter subarboj de arbo. (eo)
- In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs. Chordal graphs are a subset of the perfect graphs. They may be recognized in linear time, and several problems that are hard on other classes of graphs such as graph coloring may be solved in polynomial time when the input is chordal. The treewidth of an arbitrary graph may be characterized by the size of the cliques in the chordal graphs that contain it. (en)
- En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle. Une définition équivalente est que tout cycle sans corde possède au plus trois sommets. Les graphes cordaux, aussi appelés graphes triangulés, sont un sous-ensemble des graphes parfaits. On parle aussi de graphe triangulé. (fr)
- 弦グラフとは、グラフ理論のグラフの一つであり、その内部に存在する長さの4以上の閉路全てが弦を持つようなグラフである。ここで、弦とは、閉路を構成しないが、閉路の2頂点をつなぐ辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である（4頂点以上の誘導グラフは閉路を持たないか、弦を持つ）。 他にも、弦グラフは「単体的頂点 (simplicial vertex) を順に除去することでグラフが除去できる、という頂点の順序付けが可能である」「最小頂点分離(minimal separator)（グラフを全域グラフでなくするために除去する必要最小限なグラフ）がクリークである」「木の部分木の」といった特徴も持つ。また、rigid circuit graphsや、triangulated graphとも呼ばれる。 弦グラフは完全グラフの部分グラフである。弦グラフを多項式時間で発見できることもあり、グラフ彩色のようなグラフ一般に対しては困難な問題も、弦グラフに対しては多項式時間で解ける場合もある。グラフの(treewidth)は、それを含む弦グラフのクリークのサイズによって特徴づけられるかも知れない。 (ja)
- 그래프 이론에서 현 그래프(弦graph, 영어: chordal graph)는 큰 "구멍"이 나 있지 않는 그래프이다. (ko)
- Een graaf is chordaal als voor iedere cykel van lengte vier of meer in er een 'koorden' bestaan, dat zijn zijden die twee knopen in verbinden die in niet naast elkaar liggen, zodat er in geen cykels van vier of meer zijden zonder een koorde meer voorkomen. Men zegt dat dergelijke grafen getrianguleerd zijn. Chordale grafen zijn een deelverzameling van de perfecte grafen. Een intervalgraaf is een voorbeeld van een chordale graaf. Het is mogelijk om in lineaire tijd te bepalen of een gegeven graaf chordaal is. Men kan een maximumclique van een chordale graaf vinden in polynomiale tijd, voor algemene grafen is dit een NP-volledig probleem.
* Het aantal enkelvoudige chordale grafen met knopen is 1, 2, 4, 10, 27, 94, 393...
* Het aantal samenhangende enkelvoudige chordale grafen met knopen is 1, 1, 2, 5, 15, 58, 272... (nl)
- Nel campo matematico della teoria dei grafi, un grafo è cordale se ciascuno dei suoi cicli di quattro o più vertici ha una corda, che è uno spigolo che non fa parte del ciclo ma connette due vertici di quest'ultimo. In modo equivalente, ogni nel grafo dovrebbe avere al più tre nodi. I grafi cordali possono anche essere caratterizzati come i grafi che hanno ordinamenti di eliminazione perfetta, come i grafi nei quali ciascun separatore minimale è una cricca, e come i dei sottoalberi di un albero. Essi sono chiamati talvolta grafi a circuito rigido o grafi triangolati. I grafi cordali sono un sottoinsieme dei grafi perfetti. Possono essere riconosciuti in tempo polinomiale, e parecchi problemi che sono difficili su altre classi di grafi come la colorazione dei grafi possono essere risolti in tempo polinomiale quando l'entrata è cordale. L' di un grafo arbitrario può essere caratterizzata dalla dimensione delle cricche nei grafi cordali che la contengono. (it)
- В теории графов граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду (ребро, соединяющее две вершины цикла, но не являющееся его частью). Эквивалентное определение — если любой цикл без хорд имеет максимум три ребра. Другими словами, хордальный граф — это граф без порождённых циклов длины более чем три. Хордальные графы являются подмножеством совершенных графов. Они также иногда называются циклически жёсткими графами или триангулированными графами. (Последний термин иногда ошибочно используют для планарной триангуляции. См. максимальные планарные графы.) (ru)
- 在图论中，弦图（英語：Chordal graph）是一类含有很多弦的图。所谓“弦”，即环中跨越非邻点的一条边，或者说“捷径”（可类比圆中的弦）。弦图要求图中任意一个长度不小于4的环都须含有弦。根据该定义，弦图中每一个大环都被弦切割成若干小三角形，因此弦图也被称作三角化图。 弦图是的一种子类。算法可以在线性时间内判定一张图是否为弦图。而且，有些在一般图上困难的问题（比如图着色问题），在弦图上可被高效解决。 (zh)
- В теорії графів граф називається хордальним, якщо кожен з його циклів, що мають чотири ребра і більше, має хорду (ребро, що з'єднує дві вершини циклу, але не є його частиною). Еквівалентне визначення — якщо будь-який цикл без хорд має не більше трьох ребер. Іншими словами, хордальний граф — це граф без породжених циклів довжини більше ніж три. Хордальні графи є підмножиною досконалих графів. Їх також іноді називають циклічно жорсткими графами або тріангульованими графами. (Останній термін іноді помилково використовують для планарної тріангуляції. Див. максимальні планарні графи.) (uk)
|
| rdfs:comment
|
- Chordální graf je takový graf, který neobsahuje kružnici velikosti alespoň 4 jako indukovaný podgraf. (cs)
- In der Graphentheorie nennt man einen Graphen chordal oder trianguliert, genau dann wenn er einer der folgenden äquivalenten Bedingungen genügt:
* Jeder induzierte Kreis ist ein Dreieck. Ein Kreis ist dabei induziert, genau dann wenn zwischen seinen Knoten keine weiteren Kanten im Ursprungsgraphen existieren.
* Jeder minimale a-b-Trenner zu zwei Ecken a und b ist eine Clique.
* Jeder induzierte Teilgraph enthält eine simpliziale Ecke (Rose, 1970), also eine Ecke, deren Nachbarn eine Clique bilden.
* G ist einer Menge von Teilbäumen eines Baums (Gavril, 1974). (de)
- En grafeoterio, kordeca grafeo estas grafeo en kiu ĉiu ciklo kun pli ol kvar verticoj havas kordon, latero ne apartenanta al la ciklo sed ligas du verticojn el la ciklo. Ekvivalente, ĉiu en la grafeo estu precize 3-vertica. Oni povas ankaŭ priskribi kordecan grafeon 1.
* kiel grafeo kun perfekta forigada ordo 2.
* kiel grafeo, kies ĉiu minimuma disigilo estas plena, kaj 3.
* kiel komunaĵo inter subarboj de arbo. (eo)
- En théorie des graphes, on dit qu'un graphe est cordal si chacun de ses cycles de quatre sommets ou plus possède une corde, c'est-à-dire une arête reliant deux sommets non adjacents du cycle. Une définition équivalente est que tout cycle sans corde possède au plus trois sommets. Les graphes cordaux, aussi appelés graphes triangulés, sont un sous-ensemble des graphes parfaits. On parle aussi de graphe triangulé. (fr)
- 弦グラフとは、グラフ理論のグラフの一つであり、その内部に存在する長さの4以上の閉路全てが弦を持つようなグラフである。ここで、弦とは、閉路を構成しないが、閉路の2頂点をつなぐ辺である。また、誘導閉路グラフが常に3頂点の閉路となるようなグラフと同値である（4頂点以上の誘導グラフは閉路を持たないか、弦を持つ）。 他にも、弦グラフは「単体的頂点 (simplicial vertex) を順に除去することでグラフが除去できる、という頂点の順序付けが可能である」「最小頂点分離(minimal separator)（グラフを全域グラフでなくするために除去する必要最小限なグラフ）がクリークである」「木の部分木の」といった特徴も持つ。また、rigid circuit graphsや、triangulated graphとも呼ばれる。 弦グラフは完全グラフの部分グラフである。弦グラフを多項式時間で発見できることもあり、グラフ彩色のようなグラフ一般に対しては困難な問題も、弦グラフに対しては多項式時間で解ける場合もある。グラフの(treewidth)は、それを含む弦グラフのクリークのサイズによって特徴づけられるかも知れない。 (ja)
- 그래프 이론에서 현 그래프(弦graph, 영어: chordal graph)는 큰 "구멍"이 나 있지 않는 그래프이다. (ko)
- 在图论中，弦图（英語：Chordal graph）是一类含有很多弦的图。所谓“弦”，即环中跨越非邻点的一条边，或者说“捷径”（可类比圆中的弦）。弦图要求图中任意一个长度不小于4的环都须含有弦。根据该定义，弦图中每一个大环都被弦切割成若干小三角形，因此弦图也被称作三角化图。 弦图是的一种子类。算法可以在线性时间内判定一张图是否为弦图。而且，有些在一般图上困难的问题（比如图着色问题），在弦图上可被高效解决。 (zh)
- В теорії графів граф називається хордальним, якщо кожен з його циклів, що мають чотири ребра і більше, має хорду (ребро, що з'єднує дві вершини циклу, але не є його частиною). Еквівалентне визначення — якщо будь-який цикл без хорд має не більше трьох ребер. Іншими словами, хордальний граф — це граф без породжених циклів довжини більше ніж три. Хордальні графи є підмножиною досконалих графів. Їх також іноді називають циклічно жорсткими графами або тріангульованими графами. (Останній термін іноді помилково використовують для планарної тріангуляції. Див. максимальні планарні графи.) (uk)
- In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs. (en)
- Nel campo matematico della teoria dei grafi, un grafo è cordale se ciascuno dei suoi cicli di quattro o più vertici ha una corda, che è uno spigolo che non fa parte del ciclo ma connette due vertici di quest'ultimo. In modo equivalente, ogni nel grafo dovrebbe avere al più tre nodi. I grafi cordali possono anche essere caratterizzati come i grafi che hanno ordinamenti di eliminazione perfetta, come i grafi nei quali ciascun separatore minimale è una cricca, e come i dei sottoalberi di un albero. Essi sono chiamati talvolta grafi a circuito rigido o grafi triangolati. (it)
- Een graaf is chordaal als voor iedere cykel van lengte vier of meer in er een 'koorden' bestaan, dat zijn zijden die twee knopen in verbinden die in niet naast elkaar liggen, zodat er in geen cykels van vier of meer zijden zonder een koorde meer voorkomen. Men zegt dat dergelijke grafen getrianguleerd zijn. Chordale grafen zijn een deelverzameling van de perfecte grafen. Een intervalgraaf is een voorbeeld van een chordale graaf. (nl)
- В теории графов граф называется хордальным, если каждый из его циклов, имеющих четыре ребра и более, имеет хорду (ребро, соединяющее две вершины цикла, но не являющееся его частью). Эквивалентное определение — если любой цикл без хорд имеет максимум три ребра. Другими словами, хордальный граф — это граф без порождённых циклов длины более чем три. (ru)
|
