| dbo:abstract
|
- Turánova věta je pojem z teorie grafů. Popisuje, jak by měl vypadat graf, který má mít co nejvíce hran, a přesto nemá obsahovat úplný graf Kn-1 jako svůj podgraf. Je pojmenována podle Pála Turána. Podle Turánovy věty by takový graf měl být n-partitní. Přidáním jakékoli další hrany do n-partitního grafu v něm již někde vznikne daný nechtěný úplný podgraf Kn-1. (cs)
- Der Satz von Turán (nach Pál Turán) ist eine Aussage aus dem mathematischen Teilgebiet der Graphentheorie. Er macht eine Aussage über die maximale Anzahl von Kanten, die ein Graph mit gegebener Knotenzahl haben kann, ohne einen vollständigen Untergraphen mit Knoten enthalten zu müssen. (de)
- Le théorème de Turán est un résultat de théorie des graphes extrémaux découvert par Pál Turán. Ce théorème donne une borne supérieure sur le nombre d'arêtes dans les graphes ne contenant pas de cliques plus grosses qu'un paramètre r, et donne une caractérisation des graphes atteignant cette borne, ce sont les graphes de Turán. Ce résultat de 1941 a lancé la théorie des graphes extrémaux et possède de nombreuses preuves. (fr)
- En teoría de grafos, El teorema de Turán es un resultado sobre en número de aristas en un grafo libre de -clanes. Un grafo con vértices que no contiene ningún -clan puede ser formado de una partición del conjunto de vértices en partes de igual tamaño (o cuyo tamaño difiere en a lo más en un vértice), y conectando cualesquiera dos vértices pertenecientes a partes distintas. El grafo resultante es el grafo de Turán . El teorema de Turán establece que el grafo de Turán es aquel con el mayor número de aristas posible entre todos los grafos con vértices que son libres de -clanes. Los grafos de Turán fueron descubiertos y estudiados por el matemático húngaro Pál Turán en 1941; sin embargo, un caso especial de dicho teorema fue demostrado anteriormente por Mantel en 1907. (es)
- In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the largest or smallest graphs with given properties, and is a special case of the forbidden subgraph problem on the maximum number of edges in a graph that does not have a given subgraph. An example of an -vertex graph that does not contain any -vertex clique may be formed by partitioning the set of vertices into parts of equal or nearly equal size, and connecting two vertices by an edge whenever they belong to two different parts. The resulting graph is the Turán graph . Turán's theorem states that the Turán graph has the largest number of edges among all Kr+1-free n-vertex graphs. Turán's theorem, and the Turán graphs giving its extreme case, were first described and studied by Hungarian mathematician Pál Turán in 1941. The special case of the theorem for triangle-free graphs is known as Mantel's theorem; it was stated in 1907 by Willem Mantel, a Dutch mathematician. (en)
- Twierdzenie Turána jest twierdzeniem z teorii grafów stanowiącym oszacowanie dla liczby krawędzi w grafie niezawierającym kliki Twierdzenie oraz pierwszy opis grafów Turána pochodzi od węgierskiego matematyka Pála Turána i zostało sformułowane w roku 1941. Pięć dowodów tego twierdzenia znajduje się w Dowodach z Księgi. (pl)
- Теорема Турáна даёт ответ на вопрос о максимальном количестве рёбер в графе без полного n-вершинного подграфа. Впервые задачу о запрещённом подграфе поставил венгерский математик Пал Туран в 1941 году. (ru)
- 图兰定理是一個图论中的定理，關於 Kr+1 免除圖的邊數。簡而言之，在所有 n 點且不包(r+1)-點團的圖中，邊數最多的圖是，而且只有圖蘭圖達到邊數的最大值。圖蘭圖是將 n 點分成大小差不多的r 部分，兩點再向一部份若且惟若兩點之間有連邊。 圖蘭定理於1941年首次由匈牙利數學家圖蘭·帕爾（Turán Pál）發現，但 r=2 的情形早在 1907 年由 Mantel 提出。 (zh)
- У теорії графів, теорема Турана — це результат щодо числа ребер у графі, що не містить Kr+1. n-вершинний граф, що не містить (r + 1)-вершинну кліку, може бути побудований розбиттям множини його вершин у r частин однакового або майже однакового розміру, та з'єднанням двох вершин ребром завжди, коли вони належать двом різним частинам. Будемо називати отриманий граф граф Турана T(n,r). Теорема Турана стверджує, що граф Турана містить найбільше число ребер у класі всіх n-вершинних графів, що не містять Kr+1. Графи Турана були вперше описані та досліджені угорським математиком Палом Тураном у 1941 році, хоча частковий випадок теореми був сформульований раніше Мантелем у 1907 році. (uk)
|
| dbo:thumbnail
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 19976 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Turánova věta je pojem z teorie grafů. Popisuje, jak by měl vypadat graf, který má mít co nejvíce hran, a přesto nemá obsahovat úplný graf Kn-1 jako svůj podgraf. Je pojmenována podle Pála Turána. Podle Turánovy věty by takový graf měl být n-partitní. Přidáním jakékoli další hrany do n-partitního grafu v něm již někde vznikne daný nechtěný úplný podgraf Kn-1. (cs)
- Der Satz von Turán (nach Pál Turán) ist eine Aussage aus dem mathematischen Teilgebiet der Graphentheorie. Er macht eine Aussage über die maximale Anzahl von Kanten, die ein Graph mit gegebener Knotenzahl haben kann, ohne einen vollständigen Untergraphen mit Knoten enthalten zu müssen. (de)
- Le théorème de Turán est un résultat de théorie des graphes extrémaux découvert par Pál Turán. Ce théorème donne une borne supérieure sur le nombre d'arêtes dans les graphes ne contenant pas de cliques plus grosses qu'un paramètre r, et donne une caractérisation des graphes atteignant cette borne, ce sont les graphes de Turán. Ce résultat de 1941 a lancé la théorie des graphes extrémaux et possède de nombreuses preuves. (fr)
- Twierdzenie Turána jest twierdzeniem z teorii grafów stanowiącym oszacowanie dla liczby krawędzi w grafie niezawierającym kliki Twierdzenie oraz pierwszy opis grafów Turána pochodzi od węgierskiego matematyka Pála Turána i zostało sformułowane w roku 1941. Pięć dowodów tego twierdzenia znajduje się w Dowodach z Księgi. (pl)
- Теорема Турáна даёт ответ на вопрос о максимальном количестве рёбер в графе без полного n-вершинного подграфа. Впервые задачу о запрещённом подграфе поставил венгерский математик Пал Туран в 1941 году. (ru)
- 图兰定理是一個图论中的定理，關於 Kr+1 免除圖的邊數。簡而言之，在所有 n 點且不包(r+1)-點團的圖中，邊數最多的圖是，而且只有圖蘭圖達到邊數的最大值。圖蘭圖是將 n 點分成大小差不多的r 部分，兩點再向一部份若且惟若兩點之間有連邊。 圖蘭定理於1941年首次由匈牙利數學家圖蘭·帕爾（Turán Pál）發現，但 r=2 的情形早在 1907 年由 Mantel 提出。 (zh)
- En teoría de grafos, El teorema de Turán es un resultado sobre en número de aristas en un grafo libre de -clanes. Un grafo con vértices que no contiene ningún -clan puede ser formado de una partición del conjunto de vértices en partes de igual tamaño (o cuyo tamaño difiere en a lo más en un vértice), y conectando cualesquiera dos vértices pertenecientes a partes distintas. El grafo resultante es el grafo de Turán . El teorema de Turán establece que el grafo de Turán es aquel con el mayor número de aristas posible entre todos los grafos con vértices que son libres de -clanes. (es)
- In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the largest or smallest graphs with given properties, and is a special case of the forbidden subgraph problem on the maximum number of edges in a graph that does not have a given subgraph. (en)
- У теорії графів, теорема Турана — це результат щодо числа ребер у графі, що не містить Kr+1. n-вершинний граф, що не містить (r + 1)-вершинну кліку, може бути побудований розбиттям множини його вершин у r частин однакового або майже однакового розміру, та з'єднанням двох вершин ребром завжди, коли вони належать двом різним частинам. Будемо називати отриманий граф граф Турана T(n,r). Теорема Турана стверджує, що граф Турана містить найбільше число ребер у класі всіх n-вершинних графів, що не містять Kr+1. (uk)
|
| rdfs:label
|
- Turánova věta (cs)
- Satz von Turán (de)
- Teorema de Turán (es)
- Théorème de Turán (fr)
- Twierdzenie Turána (pl)
- Теорема Турана (ru)
- Turán's theorem (en)
- 图兰定理 (zh)
- Теорема Турана (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is rdfs:seeAlso
of | |
| is foaf:primaryTopic
of | |
