| dbo:abstract
|
- In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt. Ein induzierter Subgraph eines Graphen besteht dabei aus einer Teilmenge der Knoten und allen inzidenten Kanten. (de)
- En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo. En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos. Los grafos perfectos incluyen varias familias de grafos importantes, y sirven para unificar resultados relacionados con la coloración y los cliques en esas familias. Por ejemplo, en todos los grafos perfectos, el problema de coloración de grafos, el y el pueden ser resueltos en tiempo polinómico. Además, varios teoremas min-max importantes de combinatoria como el , pueden ser expresados en términos de la perfección de ciertos grafos asociados. La teoría de grafos perfectos fue desarrollada a partir de un resultado obtenido en 1958 por que en lenguaje moderno puede ser interpretado de modo que el complementario de un grafo bipartito es perfecto. Este resultado puede ser visto también como un equivalente simple del teorema de König, un resultado anterior que relaciona emparejamientos con cobertura de vértices en grafos bipartitos. El primer uso de la frase "grafo perfecto" parece estar en un paper de 1963 publicado por Claude Berge. En este paper, Berge unió el resultado de Gallai con varios otros resultados similares, definiendo los grafos perfectos y conjeturando una caracterización de esos grafos que luego fue probado como el Teorema fuerte de los grafos perfectos. (es)
- En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égale à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait. (fr)
- In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have . The perfect graphs include many important families of graphs and serve to unify results relating colorings and cliques in those families. For instance, in all perfect graphs, the graph coloring problem, maximum clique problem, and maximum independent set problem can all be solved in polynomial time. In addition, several important min-max theorems in combinatorics, such as Dilworth's theorem, can be expressed in terms of the perfection of certain associated graphs. A graph is 1-perfect if and only if . Then, is perfect if and only if every induced subgraph of is 1-perfect. (en)
- グラフ理論で、パーフェクトグラフ（英: perfect graph）とは、すべての誘導部分グラフの彩色数とが等しいグラフである。「理想グラフ」あるいは「完璧グラフ」と和訳されることもある。 (ja)
- 그래프 이론에서 완벽 그래프(영어: perfect graph)는 그 색칠수가 클릭과 특별한 관계를 만족시키는 그래프이다. (ko)
- Een perfecte graaf is een graaf waarvan voor elke geïnduceerde subgraaf geldt dat het cliquegetal gelijk is aan het chromatisch getal van die subgraaf. Een geïnduceerde subgraaf bestaat uit een deelverzameling van de knopen van de graaf en alleen de zijden van de graaf tussen die knopen. Het cliquegetal is het aantal knopen in de grootste volledige subgraaf van een graaf. De naam perfecte graaf wordt toegeschreven aan de Franse wiskundige Claude Berge die die in 1963 in een artikel gebruikte. Men kan in polynomiale tijd bepalen of een gegeven graaf een perfecte graaf is en ook in polynomiale tijd van een perfecte graaf het chromatisch getal, cliquegetal of stabiliteitsgetal berekenen, terwijl dit in het algemene geval een NP-compleet probleem is. Er komen in de grafentheorie verschillende perfecte grafen voor, bijvoorbeeld:
* bipartiete grafen
* chordale grafen
* volledige grafen (nl)
- Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più grande di quel sottografo. Grazie al , sappiamo dal 2002 che i grafi perfetti sono la stessa cosa dei grafi di Berge. Un grafo G è un grafo di Berge se né G né il suo complemento hanno un di lunghezza dispari uguale a 5 o superiore. I grafi perfetti comprendono molte importanti famiglie di grafi, e servono a unificare risultati che collegano le colorazioni e le cricche in quelle famiglie. Per esempio, in tutti i grafi perfetti, il problema della colorazione dei grafi, il problema della cricca massima e il problema del massimo insieme indipendente possono essere tutti risolti in tempo polinomiale. In aggiunta, parecchi importanti teoremi di minimo e massimo in combinatoria, come il , possono essere espressi in termini della perfezione di certi grafi associati. La teoria dei grafi perfetti si sviluppò da un risultato del 1958 di Tibor Gallai che in linguaggio moderno può essere interpretato affermando che il complemento di un grafo bipartito è perfetto; questo risultato può anche essere visto come un semplice equivalente del , un risultato molto anteriore che collega gli accoppiamenti e le coperture dei vertici nei grafi bipartiti. Il primo uso della locuzione "grafo perfetto" pare che sia in un saggio del 1963 di , dal quale prendono nome i grafi di Berge. In questo saggio egli unificò il risultato di Gallai con vari risultati simili definendo i grafi perfetti, e congetturò l'equivalenza delle definizioni di grafo perfetto e di grafo di Berge; la congettura di Berge fu dimostrata nel 2002 come il . (it)
- Graf doskonały (ang. perfect graph) – graf w którym liczba chromatyczna każdego podgrafu indukowanego (wierzchołkowo) jest równa rozmiarowi największej kliki tego podgrafu. W każdym grafie rozmiar kliki jest dolnym ograniczeniem na liczbę chromatyczną, ponieważ przy kolorowaniu każdy wierzchołek kliki musi otrzymać inny kolor. W grafach doskonałych to ograniczenie jest ścisłe, nie tylko dla samego grafu ale również dla wszystkich jego podgrafów. Dla innych grafów nie musi tak być: przykładowo cykl długości 5 ma liczbę chromatyczną 3, choć rozmiar największej kliki wynosi 2. Wiele istotnych klas grafów jest grafami doskonałymi, co umożliwia znalezienie łatwych rozwiązań dla niektórych problemów trudnych w ogólności. Przykładowo problem kolorowania grafów, problem kliki i problem maksymalnego zbioru niezależnego mają rozwiązania działające dla wszystkich grafów doskonałych w wielomianowym czasie. Przykładowe klasy grafów doskonałych to:
* grafy dwudzielne
* grafy krawędziowe uzyskane z grafów dwudzielnych
* grafy przedziałowe (pl)
- Em teoria dos grafos, um grafo perfeito é um grafo em que o número cromático de cada subgrafo induzido é igual ao tamanho da maior clique deste subgrafo. Em qualquer grafo, o número de clique fornece um limite inferior para o número cromático, assim como todos os vértices em uma clique devem ser atribuídos cores distintas em qualquer coloração adequada. Os grafos perfeitos são aqueles para os quais este limite inferior é apertado, não apenas no grafo em si, mas em todos os seus subgrafos induzidos. Para grafos de forma mais geral, o número cromático e o número da clique podem diferir; por exemplo, um ciclo de comprimento 5, requer três cores em qualquer coloração adequada, mas a sua maior clique tem tamanho 2. Grafos perfeitos incluem muitas famílias importantes de grafos, e servem para unificar os resultados relativos a colorações e cliques nessas famílias. Por exemplo, em todos os grafos perfeitos, o problema da coloração de grafos, o e o problema do conjunto independente máximo podem ser resolvidos em . Além disso, vários teoremas importantes min-max em análise combinatória, como o , podem ser expressos em termos da perfeição de alguns grafos associados. A teoria dos grafos perfeitos desenvolveu-se a partir um resultado de 1958 de Tibor Gallai que em linguagem moderna, pode ser interpretado como indicando que o complementar de um grafo bipartido é perfeito; este resultado também pode ser visto como um simples equivalente do , um resultado bem mais anterior relacionando acoplamentos e coberturas de vértices em grafos bipartidos. O primeiro uso da expressão "grafo perfeito" parece estar em um artigo de 1963 de Claude Berge. Neste artigo ele unificou o resultado de Gallai com vários resultados semelhantes através da definição de grafos perfeitos e conjecturando uma caracterização destes grafos que mais tarde foi comprovado como o Teorema Forte dos Grafos Perfeitos. (pt)
- Досконалим графом називається граф, у якому хроматичне число будь-якого породженого підграфу дорівнює розміру максимальної кліки цього підграфу. Відповідно до сильної теореми про досконалі графи, досконалі графи — це те саме, що й графи Берже. Граф G є графом Берже, якщо ні G, ні його додаток не мають породжених циклів, довжиною більше 5 ребер. Досконалий граф містить у собі багато досконалих сімейств графів, та забезпечують уніфікацію результатів, пов'язаних із розфарбуванням та кліками цих сімейств. Наприклад, для всіх досконалих графів задача про розфарбовування , задача про максимальну кліку та задача про максимальну незалежну множину можуть бути розв'язані за поліномінальний час. Крім того, декілька важливих мінімаксних теорем комбінаторики, такі як теорема Ділуорса, можуть бути виражені в термінах досконалих та деяких пов'язаних з ними графів. Теорія досконалих графів почала свій розвиток після роботи Тібора Галаї 1958 року, що може бути інтерпретована на сучасній мові як твердження: доповнення двочасткового графу є досконалим графом. Також це можна розглядати як простий еквівалент до теореми Кьоніга, а значно раніший результат стосується паросполучень та покриття вершин у двочасткових графах. Вперше словосполучення «досконалий граф» було вжите в 1963 році у статті Клауді Бержа, після якого було інтерпретоване як «граф Берже». У цій статті вчений пов'язав результати Галая з деякими іншими шляхом визначення досконалих графів та запропонував гіпотезу про ідентичність досконалих графів та «графів Берже», що була доведена в 2002 році як сильна теорема про досконалі графи. (uk)
- В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины (5 и более рёбер). Совершенные графы включают много важных семейств графов и обеспечивают унификацию результатов, связанных с раскраской и кликами этих семейств. Например, во всех совершенных графах задача раскраски, задача о максимальной клике и задача о максимальном независимом множестве могут быть решены за полиномиальное время. Вдобавок, некоторые важные минимаксные теоремы комбинаторики, такие как теорема Дилуорса, могут быть сформулированы в терминах совершенных и некоторых связанных с ними графов. Теория совершенных графов развивается с работы 1958-го года , которая на современном языке может быть интерпретирована как утверждение, что дополнение двудольного графа есть совершенный граф. Этот результат можно рассматривать как простой эквивалент теоремы Кёнига, значительно более ранний результат относительно паросочетаний и вершинных покрытий в двудольных графах. Первое применение термина «совершенный граф» появилось в 1963 году в статье , откуда и появилось название «графы Бержа». В этой статье он объединил результат Галаи с некоторыми похожими результатами путём определения совершенных графов и высказал гипотезу об эквивалентности совершенных графов и графов Бержа. Гипотеза доказана в 2002 году как строгая теорема о совершенных графах. (ru)
|
| rdfs:comment
|
- In der Graphentheorie heißt ein Graph perfekt, wenn für jeden induzierten Subgraphen gilt, dass seine Cliquenzahl mit seiner chromatischen Zahl übereinstimmt. Ein induzierter Subgraph eines Graphen besteht dabei aus einer Teilmenge der Knoten und allen inzidenten Kanten. (de)
- En théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égale à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait. (fr)
- グラフ理論で、パーフェクトグラフ（英: perfect graph）とは、すべての誘導部分グラフの彩色数とが等しいグラフである。「理想グラフ」あるいは「完璧グラフ」と和訳されることもある。 (ja)
- 그래프 이론에서 완벽 그래프(영어: perfect graph)는 그 색칠수가 클릭과 특별한 관계를 만족시키는 그래프이다. (ko)
- En teoría de grafos, un grafo perfecto es un grafo en el que el número cromático de cada subgrafo inducido es igual al tamaño del mayor clique de ese subgrafo. En cualquier grafo, el número clique provee una cota inferior para el número cromático, ya que a cada uno de los vértices en un clique se les debe asignar un color distinto para obtener una coloración propia. Los grafos perfectos son aquellos para los cuales esta cota inferior es exacta no sólo para el grafo en sí, sino para todos los subgrafos inducidos. En los grafos en general, el número cromático y el número de clique pueden ser distintos. Por ejemplo, un ciclo de 5 vértices requiere tres colores para obtener una coloración correcta, pero el clique mayor es de tamaño dos. (es)
- In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if for all we have . A graph is 1-perfect if and only if . Then, is perfect if and only if every induced subgraph of is 1-perfect. (en)
- Nella teoria dei grafi, un grafo perfetto è un grafo nel quale il numero cromatico di ogni sottografo indotto è uguale alla dimensione della cricca più grande di quel sottografo. Grazie al , sappiamo dal 2002 che i grafi perfetti sono la stessa cosa dei grafi di Berge. Un grafo G è un grafo di Berge se né G né il suo complemento hanno un di lunghezza dispari uguale a 5 o superiore. (it)
- Een perfecte graaf is een graaf waarvan voor elke geïnduceerde subgraaf geldt dat het cliquegetal gelijk is aan het chromatisch getal van die subgraaf. Een geïnduceerde subgraaf bestaat uit een deelverzameling van de knopen van de graaf en alleen de zijden van de graaf tussen die knopen. Het cliquegetal is het aantal knopen in de grootste volledige subgraaf van een graaf. De naam perfecte graaf wordt toegeschreven aan de Franse wiskundige Claude Berge die die in 1963 in een artikel gebruikte. Er komen in de grafentheorie verschillende perfecte grafen voor, bijvoorbeeld: (nl)
- В теории графов совершенным графом называется граф, в котором хроматическое число любого порождённого подграфа равно размеру максимальной клики этого подграфа. Благодаря строгой теореме о совершенных графах, с 2002 года известно, что совершенные графы — это то же самое, что и графы Бержа. Граф G является графом Бержа если ни G, ни его дополнение не имеет порождённых циклов нечётной длины (5 и более рёбер). (ru)
- Graf doskonały (ang. perfect graph) – graf w którym liczba chromatyczna każdego podgrafu indukowanego (wierzchołkowo) jest równa rozmiarowi największej kliki tego podgrafu. W każdym grafie rozmiar kliki jest dolnym ograniczeniem na liczbę chromatyczną, ponieważ przy kolorowaniu każdy wierzchołek kliki musi otrzymać inny kolor. W grafach doskonałych to ograniczenie jest ścisłe, nie tylko dla samego grafu ale również dla wszystkich jego podgrafów. Dla innych grafów nie musi tak być: przykładowo cykl długości 5 ma liczbę chromatyczną 3, choć rozmiar największej kliki wynosi 2. (pl)
- Em teoria dos grafos, um grafo perfeito é um grafo em que o número cromático de cada subgrafo induzido é igual ao tamanho da maior clique deste subgrafo. Em qualquer grafo, o número de clique fornece um limite inferior para o número cromático, assim como todos os vértices em uma clique devem ser atribuídos cores distintas em qualquer coloração adequada. Os grafos perfeitos são aqueles para os quais este limite inferior é apertado, não apenas no grafo em si, mas em todos os seus subgrafos induzidos. Para grafos de forma mais geral, o número cromático e o número da clique podem diferir; por exemplo, um ciclo de comprimento 5, requer três cores em qualquer coloração adequada, mas a sua maior clique tem tamanho 2. (pt)
- Досконалим графом називається граф, у якому хроматичне число будь-якого породженого підграфу дорівнює розміру максимальної кліки цього підграфу. Відповідно до сильної теореми про досконалі графи, досконалі графи — це те саме, що й графи Берже. Граф G є графом Берже, якщо ні G, ні його додаток не мають породжених циклів, довжиною більше 5 ребер. (uk)
|
