Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure.Results in extremal graph theory deal with quantitative connections between various graph properties, both global (such as the number of vertices and edges) and local (such as the existence of specific subgraphs), and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy?A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objec
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Extremal graph theory (en)
- Extremální teorie grafů (cs)
- Extremale Graphentheorie (de)
- Teoría de grafos extremales (es)
- Théorie des graphes extrémaux (fr)
- Экстремальная теория графов (ru)
- Екстремальна теорія графів (uk)
|
| rdfs:comment
| - Extremální teorie grafů je oblastí teorie grafů, která zkoumá vztah kvantitativních parametrů konečných grafů. Extremální teorie grafů též může být vnímána jako obor , která zkoumá podobné problémy pro další diskrétní struktury (zejména pro množinové systémy a hypergrafy). (cs)
- En théorie des graphes, un graphe extrémal (anglais : extremal graph) par rapport à une propriété est un graphe tel que l'ajout de n'importe quelle arête amène le graphe à vérifier la propriété . L'étude des graphes extrémaux se décompose en deux sujets : la recherche de bornes inférieures sur le nombre d'arêtes nécessaires à assurer la propriété (voire sur d'autres paramètres comme le degré minimum) et la caractérisation des graphes extrémaux proprement dits. L'étude des graphes extrémaux est une branche de l'étude combinatoire des graphes. (fr)
- Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа. (ru)
- Екстремальна теорія графів — це гілка теорії графів. Екстремальна теорія графів вивчає екстремальні (максимальні або мінімальні) властивості графів, які задовольняють певним умовам. Екстремальність може стосуватися різних інваріантів графів, таких як порядок, розмір або обхват. В абстрактнішому сенсі, теорія вивчає, як глобальні властивості графу впливають на локальні підструктури графу. (uk)
- Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure.Results in extremal graph theory deal with quantitative connections between various graph properties, both global (such as the number of vertices and edges) and local (such as the existence of specific subgraphs), and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy?A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objec (en)
- Die extremale Graphentheorie ist ein Teilgebiet der Mathematik. Sie untersucht, welche Graphen einer gegebenen Klasse (wie der Klasse der Graphen ohne Hamiltonkreis) einen bestimmten Graphenparameter (wie die maximale Anzahl von Kanten oder die Kantendichte) maximieren oder minimieren. Ein Ergebnis der extremalen Graphentheorie ist beispielsweise, dass Graphen mit Knoten, die keinen Kreis der Länge 3 enthalten, höchstens Kanten besitzen. Das ist ein Spezialfall des Satzes von Pál Turán (1941), der die extremale Graphentheorie begründete: . (de)
- La teoría de grafos extremales es una rama de las matemáticas que estudia cómo es que propiedades globales de un grafo pueden influir en su subestructura local. Esta rama abarca un vasto número de resultados que describen cómo ciertas propiedades de las gráficas - número de vértices, número de aristas, densidad de aristas, número cromático, o cintura, por ejemplo - garantizan la existencia de ciertas subestructuras locales. (es)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| quote
| - Extremal graph theory, in its strictest sense, is a branch of graph theory developed and loved by Hungarians. (en)
|
| source
| |
| width
| |
| has abstract
| - Extremální teorie grafů je oblastí teorie grafů, která zkoumá vztah kvantitativních parametrů konečných grafů. Extremální teorie grafů též může být vnímána jako obor , která zkoumá podobné problémy pro další diskrétní struktury (zejména pro množinové systémy a hypergrafy). (cs)
- Extremal graph theory is a branch of combinatorics, itself an area of mathematics, that lies at the intersection of extremal combinatorics and graph theory. In essence, extremal graph theory studies how global properties of a graph influence local substructure.Results in extremal graph theory deal with quantitative connections between various graph properties, both global (such as the number of vertices and edges) and local (such as the existence of specific subgraphs), and problems in extremal graph theory can often be formulated as optimization problems: how big or small a parameter of a graph can be, given some constraints that the graph has to satisfy?A graph that is an optimal solution to such an optimization problem is called an extremal graph, and extremal graphs are important objects of study in extremal graph theory. Extremal graph theory is closely related to fields such as Ramsey theory, spectral graph theory, computational complexity theory, and additive combinatorics, and frequently employs the probabilistic method. (en)
- Die extremale Graphentheorie ist ein Teilgebiet der Mathematik. Sie untersucht, welche Graphen einer gegebenen Klasse (wie der Klasse der Graphen ohne Hamiltonkreis) einen bestimmten Graphenparameter (wie die maximale Anzahl von Kanten oder die Kantendichte) maximieren oder minimieren. Ein Ergebnis der extremalen Graphentheorie ist beispielsweise, dass Graphen mit Knoten, die keinen Kreis der Länge 3 enthalten, höchstens Kanten besitzen. Das ist ein Spezialfall des Satzes von Pál Turán (1941), der die extremale Graphentheorie begründete: Satz von Turán: Ein Graph mit n Knoten ohne p-Clique (vollständiger Untergraph mit p Knoten), , hat maximal Kanten. Definiert man zu einem Graphen die Zahl als die maximale Kantenzahl, die ein Graph mit Knoten und ohne einen zu isomorphen Untergraphen haben kann, so lässt sich diese Aussage zu umformulieren, wobei der vollständige Graph mit Knoten ist. Bezeichnet man mit den Kreisgraphen mit Knoten, so erhält man als weiteres Beispiel . Der Graph, der aus durch Hinzunahme eines weiteren Knotens und einer Kante entsteht, hat keinen zu isomorphen Untergraphen und Kanten (siehe nebenstehende Zeichnung für ). Die Hinzunahme einer weiteren Kante führt offenbar zu einem zu isomorphen Untergraphen. (de)
- La teoría de grafos extremales es una rama de las matemáticas que estudia cómo es que propiedades globales de un grafo pueden influir en su subestructura local. Esta rama abarca un vasto número de resultados que describen cómo ciertas propiedades de las gráficas - número de vértices, número de aristas, densidad de aristas, número cromático, o cintura, por ejemplo - garantizan la existencia de ciertas subestructuras locales. Uno de los principales objetos de estudio de esta área de teoría de grafos son los grafos extremales, que son o bien maximales o minimales con respecto a algún parámetro global, y tales que contienen (o no contienen) cierta subestructura local - ya sea un clique, o una coloración de sus aristas. (es)
- En théorie des graphes, un graphe extrémal (anglais : extremal graph) par rapport à une propriété est un graphe tel que l'ajout de n'importe quelle arête amène le graphe à vérifier la propriété . L'étude des graphes extrémaux se décompose en deux sujets : la recherche de bornes inférieures sur le nombre d'arêtes nécessaires à assurer la propriété (voire sur d'autres paramètres comme le degré minimum) et la caractérisation des graphes extrémaux proprement dits. L'étude des graphes extrémaux est une branche de l'étude combinatoire des graphes. (fr)
- Экстремальная теория графов — это ветвь теории графов. Экстремальная теория графов изучает экстремальные (максимальные или минимальные) свойства графов, удовлетворяющих определённым условиям. Экстремальность может относиться к различным инвариантам графов, таким как порядок, размер или обхват. В более абстрактном смысле теория изучает, как глобальные свойства графа влияют на локальные подструктуры графа. (ru)
- Екстремальна теорія графів — це гілка теорії графів. Екстремальна теорія графів вивчає екстремальні (максимальні або мінімальні) властивості графів, які задовольняють певним умовам. Екстремальність може стосуватися різних інваріантів графів, таких як порядок, розмір або обхват. В абстрактнішому сенсі, теорія вивчає, як глобальні властивості графу впливають на локальні підструктури графу. (uk)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
