Graph minor (original) (raw)
Minor grafu je rozšířením pojmu podgrafu.
| Property | Value |
|---|---|
| dbo:abstract | Minor grafu je rozšířením pojmu podgrafu. (cs) Στη θεωρία γραφημάτων, ένα μη-κατευθυνόμενο γράφημα Η καλείται έλασσον του γραφήματος G, αν Η μπορεί να σχηματιστεί από το G διαγράφοντας ακμές και κορυφές και από τις συγχωνευμένες άκρες. Η θεωρία των ελασσόνων γραφημάτων ξεκίνησε με το σύμφωνα με το οποίο ένα γράφημα είναι επίπεδο αν και μόνο αν οι ελάσσονες του δεν περιλαμβάνουν το πλήρες Κ5 γράφημα ούτε το πλήρες διμερές γράφημα K3,3. Το θεώρημα Robertson-Seymour συνεπάγεται ότι ένας ανάλογος απαγορευμένος ελάσσων χαρακτηρισμός υπάρχει για κάθε ιδιότητα των γραφημάτων που διατηρούνται με διαγραφές και συγχωνεύσεις κουφών . Για κάθε σταθερό γράφημα H, είναι δυνατόν να ελεγχθεί αν Η είναι έλασσον ενός γραφήματος εισόδου G σε πολυωνυμικό χρόνο μαζί με τον απαγορευμένο ελάσσονα χαρακτηρισμό βάση του οποίου κάθε γράφημα ιδιότητας το οποίο δημιουργείται από διαγραφές και συγχωνεύσεις μπορεί να αναγνωριστεί σε πολυωνυμικό χρόνο. Άλλα αποτελέσματα και τις εικασίες που αφορούν ελάσσονα γραφήματα περιλαμβάνουν το θεώρημα δομής γραφήματος, σύμφωνα με το οποίο τα γραφήματα που δεν έχουν Η ως ένας έλασσον, μπορούν να σχηματιστούν από την ένωση απλούστερων τμημάτων, και την εικασία Hadwiger που αφορά στην αδυναμία να χρωματίσουν ένα γράφημα με την ύπαρξη ενός μεγάλου πλήρες γραφήματος ως έλασσον αυτού. Σημαντικές μεταβλητές των ελάσσων γραφημάτων περιλαμβάνουν τα τοπολογικά ελάσσων και ελάσσων γραφήματα συγκέντρωσης. (el) In der Graphentheorie sind Minoren gewisse Graphen, die sich durch Kantenkontraktion und durch Weglassen von Kanten oder Knoten aus einem anderen Graphen gewinnen lassen. Die Minorenrelation ist neben der Teilgraphenrelation und der Unterteilungsrelation eine der wichtigsten Relationen der Graphentheorie und erlaubt viele tiefgehende Sätze wie z. B. den Satz von Kuratowski oder das Minorentheorem von Robertson und Seymour. (de) In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time; together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time. Other results and conjectures involving graph minors include the graph structure theorem, according to which the graphs that do not have H as a minor may be formed by gluing together simpler pieces, and Hadwiger's conjecture relating the inability to color a graph to the existence of a large complete graph as a minor of it. Important variants of graph minors include the topological minors and immersion minors. (en) En teoría de grafos, un grafo H se denomina menor del grafo G si se puede formar H a partir de G eliminando aristas y vértices y mediante la contracción de aristas. La teoría de los menores de grafo comenzó con el teorema de Wagner, que afirma que un grafo es plano si y solo si sus menores no incluyen ni el grafo completo K5 ni el grafo bipartito completo K3,3. El implica que existe una caracterización de menores prohibidos análogo para cada propiedad de los grafos que se conserva mediante eliminaciones y contracciones de arista. Para cada grafo fijo H, es posible probar si H es un menor de un grafo de entrada G en complejidad temporal; junto con la caracterización menor prohibida, esto implica que cada propiedad del grafo preservada por eliminaciones y contracciones puede reconocerse en tiempo polinomial. Otros resultados y conjeturas que involucran grafos menores incluyen el , según el cual los grafos que no tienen H como menor pueden formarse pegando piezas más simples, y la que relaciona la incapacidad de colorear un grafo con la existencia de un gran grafo completo como menor. Las variantes importantes de los menores de grafos incluyen los menores topológicos y los menores de inmersión. (es) La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011. (fr) 그래프 이론에서 마이너(영어: minor)는 어떤 그래프의 변들을 축약시켜 얻는 그래프이다. (ko) In de grafentheorie, een onderdeel van de wiskunde, is een minor van een graaf een graaf die uit kan worden voortgebracht door knopen te verwijderen, zijden te verwijderen, of zijden samen te trekken. Minoren spelen een belangrijke rol bij het karakteriseren van eigenschappen van grafen, zoals planariteit. (nl) Минор в теории графов — граф для заданного графа , который может быть образован из удалением рёбер и вершин и стягиванием рёбер. Теория миноров графов началась с теоремы Вагнера, гласящей, что граф планарен в том и только в том случае, когда в его миноры не входят ни в полный граф K5, ни в полный двудольный граф K3,3. Из теоремы Робертсона — Сеймура следует, что аналоги характеризации запрещёнными минорами существуют для любого свойства графов, которые сохраняются при удалениях и стягивании рёбер. Для любого графа H можно проверить, является ли H минором входного графа G за полиномиальное время. Вместе с характеризацией запрещёнными минорами из этого следует, что любое свойство графа, сохраняющееся при удалениях и стягиваниях, может быть распознано за полиномиальное время. Среди других результатов и гипотез, использующих миноры графов, находятся теорема о структуре графа, согласно которой графы, не содержащие H в качестве минора, могут быть образованы склеиванием более простых частей, и гипотеза Хадвигера, связывающая невозможность раскраски графа с существованием большого полного графа в качестве его минора. Важными вариантами миноров графов являются топологические миноры и погружённые миноры. (ru) 在图论中，如果无向图H可以通过图G删除边和顶点或收缩边得到，则称H为G的子式（minor）或次图。 图子式的提出源自瓦格纳定理，这个定理表明：当且仅当一个图不存在完全图K5和完全二分图K3,3的子式时，这个图才是平面图。表明，对于任何在图上删除点或边或收缩边保留的性质，类似的（forbidden minor characterization）也存在。给定图G和图H，可以在多项式时间内判断H是否是G的子式。连同上述禁子式表征，这意味着任何删除点或边和收缩边保留的图的属性可以在多项式时间内被识别。其他涉及到图子式的定理和猜想包括、等。 (zh) В теорії графів неорієнтований граф Н називається мінором графа G, якщо H можна сформувати з G видаленням ребер і вершин або стягуванням ребер. Теорія мінорів графів почалася з теореми Вагнера, в якій говориться, що граф є планарним, якщо і тільки якщо його мінори не включають в себе ні повний граф K5, ні повний двочастковий граф K3,3.. Теорема Робертсона — Сеймура передбачає, що аналогічна характеризація забороненими мінорами існує для кожної властивості графів, що зберігається за рахунок видалення вершин і стягування ребер. Для кожного фіксованого графа H можна перевірити, чи є Н мінором вхідного графа G за поліноміальний час. Разом з характеризацією забороненими мінорами це означає, що кожна властивість графа, збережена при діленні та скороченнях, може бути розпізнана за поліноміальний час. Інші результати і домисли за участю мінора графа включають теорему структури графа, відповідно до якої графи, в яких немає Н як мінору, можуть бути утворені шляхом склеювання більш простих частин. А гіпотеза Хадвігера описує неможливість пофарбувати графи згідно існуючого великого повного графа, як і його мінор. Важливі варіанти мінорів графа включають топологічні мінори і занурені мінори. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/GraphMinorExampleA.svg?width=300 |
| dbo:wikiPageExternalLink | http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ http://www.math.gatech.edu/~thomas/PAP/hadwiger.pdf https://www.ams.org/notices/200209/rev-pegg.pdf http://www2.renyi.hu/~p_erdos/1980-10.pdf https://web.archive.org/web/20090318165333/http:/www2.renyi.hu/~p_erdos/1980-10.pdf http://erikdemaine.org/papers/DiameterTreewidth_Algorithmica/ http://www.stanford.edu/~plotkin/lminors.ps http://people.math.gatech.edu/~thomas/PAP/bcc.pdf |
| dbo:wikiPageID | 353042 (xsd:integer) |
| dbo:wikiPageLength | 36043 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096538418 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Multigraph dbr:Shallow_minor dbr:Binary_relation dbr:Degeneracy_(graph_theory) dbc:Graph_minor_theory dbr:Path_graph dbr:Pathwidth dbr:Paul_Seymour_(mathematician) dbr:Cubic_graph dbr:Undirected_graph dbr:Decision_problem dbr:Degree_(graph_theory) dbr:Pseudoforest dbr:Robertson–Seymour_theorem dbr:1-planar_graph dbc:Graph_theory_objects dbr:Complete_bipartite_graph dbr:Complete_graph dbr:Crossing_number_(graph_theory) dbr:Genus_(mathematics) dbr:Petersen_graph dbr:Clique-sum dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Graph_structure_theorem dbr:Apex_graph dbr:Combinatorica dbr:Deep_result dbr:Planar_separator_theorem dbr:Mathematical_Proceedings_of_the_Cambridge_Philosophical_Society dbr:Matroid_minor dbr:Peripheral_cycle dbr:Transitive_relation dbr:Tree_(graph_theory) dbr:Treewidth dbr:W._T._Tutte dbr:Wagner_graph dbr:Well-quasi-ordering dbr:Galactic_algorithm dbr:American_Mathematical_Society dbr:Cycle_graph dbr:Edge_coloring dbr:Forbidden_graph_characterization dbr:Bridge_(graph_theory) dbr:Diameter_(graph_theory) dbr:Four_color_theorem dbr:Graph_drawing dbr:Graph_embedding dbr:Graph_isomorphism dbr:Graph_theory dbr:Journal_of_Combinatorial_Theory dbr:Journal_of_the_ACM dbr:Journal_of_the_American_Mathematical_Society dbr:Knuth's_up-arrow_notation dbr:Tree-depth dbr:Rank_(graph_theory) dbr:Hadwiger_conjecture_(graph_theory) dbr:Snark_theorem dbr:Big_O_notation dbr:Bipartite_graph dbr:Edge_contraction dbr:Distance_(graph_theory) dbr:Bulletin_of_the_American_Mathematical_Society dbr:Planar_graph dbr:Polynomial_time dbr:Infinity dbr:Neil_Robertson_(mathematician) dbr:Klaus_Wagner dbr:Loop_(graph_theory) dbr:Utility_graph dbr:Vertex_(graph_theory) dbr:European_Journal_of_Combinatorics dbr:Planarization dbr:Multiple_edge dbr:Partial_order dbr:Wagner's_theorem dbr:2-manifold dbr:Hamiltonian_cycle dbr:Forbidden_minors dbr:Minimal_element dbr:Cut-edge dbr:Sparse_graph dbr:Subdivision_(graph_theory) dbr:Bipartite_minor dbr:File:GraphMinorExampleA.svg dbr:File:GraphMinorExampleB.svg dbr:File:GraphMinorExampleC.svg dbr:Odd_minor |
| dbp:title | Graph Minor (en) |
| dbp:urlname | GraphMinor (en) |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Details dbt:Frac dbt:Harvtxt dbt:Math dbt:Mathworld dbt:Mvar dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Short_description dbt:Sub |
| dct:subject | dbc:Graph_minor_theory dbc:Graph_theory_objects |
| gold:hypernym | dbr:Planar |
| rdf:type | yago:Object100002684 yago:PhysicalEntity100001930 yago:WikicatGraphTheoryObjects |
| rdfs:comment | Minor grafu je rozšířením pojmu podgrafu. (cs) In der Graphentheorie sind Minoren gewisse Graphen, die sich durch Kantenkontraktion und durch Weglassen von Kanten oder Knoten aus einem anderen Graphen gewinnen lassen. Die Minorenrelation ist neben der Teilgraphenrelation und der Unterteilungsrelation eine der wichtigsten Relationen der Graphentheorie und erlaubt viele tiefgehende Sätze wie z. B. den Satz von Kuratowski oder das Minorentheorem von Robertson und Seymour. (de) La notion de mineur d'un graphe est un concept de théorie des graphes. Il a été défini et étudié par Robertson et Seymour dans une série d'articles intitulée Graph minors (I à XXIII), publiée dans le Journal of Combinatorial Theory entre 1983 et 2011. (fr) 그래프 이론에서 마이너(영어: minor)는 어떤 그래프의 변들을 축약시켜 얻는 그래프이다. (ko) In de grafentheorie, een onderdeel van de wiskunde, is een minor van een graaf een graaf die uit kan worden voortgebracht door knopen te verwijderen, zijden te verwijderen, of zijden samen te trekken. Minoren spelen een belangrijke rol bij het karakteriseren van eigenschappen van grafen, zoals planariteit. (nl) 在图论中，如果无向图H可以通过图G删除边和顶点或收缩边得到，则称H为G的子式（minor）或次图。 图子式的提出源自瓦格纳定理，这个定理表明：当且仅当一个图不存在完全图K5和完全二分图K3,3的子式时，这个图才是平面图。表明，对于任何在图上删除点或边或收缩边保留的性质，类似的（forbidden minor characterization）也存在。给定图G和图H，可以在多项式时间内判断H是否是G的子式。连同上述禁子式表征，这意味着任何删除点或边和收缩边保留的图的属性可以在多项式时间内被识别。其他涉及到图子式的定理和猜想包括、等。 (zh) Στη θεωρία γραφημάτων, ένα μη-κατευθυνόμενο γράφημα Η καλείται έλασσον του γραφήματος G, αν Η μπορεί να σχηματιστεί από το G διαγράφοντας ακμές και κορυφές και από τις συγχωνευμένες άκρες. Η θεωρία των ελασσόνων γραφημάτων ξεκίνησε με το σύμφωνα με το οποίο ένα γράφημα είναι επίπεδο αν και μόνο αν οι ελάσσονες του δεν περιλαμβάνουν το πλήρες Κ5 γράφημα ούτε το πλήρες διμερές γράφημα K3,3. Το θεώρημα Robertson-Seymour συνεπάγεται ότι ένας ανάλογος απαγορευμένος ελάσσων χαρακτηρισμός υπάρχει για κάθε ιδιότητα των γραφημάτων που διατηρούνται με διαγραφές και συγχωνεύσεις κουφών . Για κάθε σταθερό γράφημα H, είναι δυνατόν να ελεγχθεί αν Η είναι έλασσον ενός γραφήματος εισόδου G σε πολυωνυμικό χρόνο μαζί με τον απαγορευμένο ελάσσονα χαρακτηρισμό βάση του οποίου κάθε γράφημα ιδιότητας το οποίο (el) In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges. The theory of graph minors began with Wagner's theorem that a graph is planar if and only if its minors include neither the complete graph K5 nor the complete bipartite graph K3,3. The Robertson–Seymour theorem implies that an analogous forbidden minor characterization exists for every property of graphs that is preserved by deletions and edge contractions.For every fixed graph H, it is possible to test whether H is a minor of an input graph G in polynomial time; together with the forbidden minor characterization this implies that every graph property preserved by deletions and contractions may be recognized in polynomial time. (en) En teoría de grafos, un grafo H se denomina menor del grafo G si se puede formar H a partir de G eliminando aristas y vértices y mediante la contracción de aristas. La teoría de los menores de grafo comenzó con el teorema de Wagner, que afirma que un grafo es plano si y solo si sus menores no incluyen ni el grafo completo K5 ni el grafo bipartito completo K3,3. El implica que existe una caracterización de menores prohibidos análogo para cada propiedad de los grafos que se conserva mediante eliminaciones y contracciones de arista. (es) Минор в теории графов — граф для заданного графа , который может быть образован из удалением рёбер и вершин и стягиванием рёбер. Теория миноров графов началась с теоремы Вагнера, гласящей, что граф планарен в том и только в том случае, когда в его миноры не входят ни в полный граф K5, ни в полный двудольный граф K3,3. Из теоремы Робертсона — Сеймура следует, что аналоги характеризации запрещёнными минорами существуют для любого свойства графов, которые сохраняются при удалениях и стягивании рёбер. (ru) В теорії графів неорієнтований граф Н називається мінором графа G, якщо H можна сформувати з G видаленням ребер і вершин або стягуванням ребер. Теорія мінорів графів почалася з теореми Вагнера, в якій говориться, що граф є планарним, якщо і тільки якщо його мінори не включають в себе ні повний граф K5, ні повний двочастковий граф K3,3.. Теорема Робертсона — Сеймура передбачає, що аналогічна характеризація забороненими мінорами існує для кожної властивості графів, що зберігається за рахунок видалення вершин і стягування ребер. Для кожного фіксованого графа H можна перевірити, чи є Н мінором вхідного графа G за поліноміальний час. Разом з характеризацією забороненими мінорами це означає, що кожна властивість графа, збережена при діленні та скороченнях, може бути розпізнана за поліноміальний (uk) |
| rdfs:label | Minor (teorie grafů) (cs) Minor (Graphentheorie) (de) Ελάσσων γράφος (el) Menor (teoría de grafos) (es) Graph minor (en) Mineur (théorie des graphes) (fr) 그래프 마이너 (ko) Minor (grafentheorie) (nl) Минор графа (ru) Мінор графа (uk) 图子式 (zh) |
| owl:sameAs | freebase:Graph minor yago-res:Graph minor wikidata:Graph minor dbpedia-cs:Graph minor dbpedia-de:Graph minor dbpedia-el:Graph minor dbpedia-es:Graph minor dbpedia-fr:Graph minor dbpedia-hr:Graph minor dbpedia-hu:Graph minor dbpedia-ko:Graph minor dbpedia-nl:Graph minor dbpedia-ru:Graph minor dbpedia-uk:Graph minor dbpedia-zh:Graph minor https://global.dbpedia.org/id/54GPa |
| prov:wasDerivedFrom | wikipedia-en:Graph_minor?oldid=1096538418&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/GraphMinorExampleA.svg wiki-commons:Special:FilePath/GraphMinorExampleB.svg wiki-commons:Special:FilePath/GraphMinorExampleC.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Graph_minor |
| is dbo:wikiPageRedirects of | dbr:Minor_(graph_theory) dbr:Topological_minor dbr:Graph-minor dbr:Minor-closed_graph_family dbr:Minor_(graph) dbr:Minor_(of_a_graph) dbr:Minor_of_a_graph |
| is dbo:wikiPageWikiLink of | dbr:Queue_number dbr:Minor_(graph_theory) dbr:Mac_Lane's_planarity_criterion dbr:Shallow_minor dbr:Topological_minor dbr:Apollonian_network dbr:Julia_Chuzhoy dbr:Pathwidth dbr:Cycle_basis dbr:Kuratowski's_theorem dbr:Complete_graph dbr:Obstruction dbr:Glossary_of_graph_theory dbr:Graph_coloring dbr:Graph_homomorphism dbr:Boxicity dbr:Branch-decomposition dbr:Erdős–Pósa_theorem dbr:Apex_graph dbr:Linkless_embedding dbr:Logic_of_graphs dbr:Cactus_graph dbr:Snark_(graph_theory) dbr:Clique_(graph_theory) dbr:Combinatorics:_The_Rota_Way dbr:Feedback_arc_set dbr:Friedman's_SSCG_function dbr:Fulkerson_Prize dbr:Halin's_grid_theorem dbr:Planar_separator_theorem dbr:Steinitz's_theorem dbr:Matroid_minor dbr:Treewidth dbr:Wagner_graph dbr:Well-quasi-ordering dbr:GNRS_conjecture dbr:Galactic_algorithm dbr:Lattice_graph dbr:Three_utilities_problem dbr:Trémaux_tree dbr:Erik_Demaine dbr:Forbidden_graph_characterization dbr:Otakar_Borůvka dbr:Graph_amalgamation dbr:Graph_flattenability dbr:Graph_operations dbr:Graph_property dbr:Graphic_matroid dbr:Kelmans–Seymour_conjecture dbr:Ken-ichi_Kawarabayashi dbr:Hadwiger_conjecture_(graph_theory) dbr:Hadwiger_number dbr:Baker's_technique dbr:Courcelle's_theorem dbr:Pebble_game dbr:Albertson_conjecture dbr:Bidimensionality dbr:Edge_contraction dbr:Hereditary_property dbr:Herschel_graph dbr:Toroidal_graph dbr:Diamond_graph dbr:Borůvka's_algorithm dbr:Hugo_Hadwiger dbr:Graph-minor dbr:Metric_dimension_(graph_theory) dbr:Neil_Robertson_(mathematician) dbr:Klaus_Wagner dbr:Eulerian_matroid dbr:List_of_unsolved_problems_in_mathematics dbr:Partial_k-tree dbr:Planarization dbr:Planar_cover dbr:Pfaffian_orientation dbr:The_Petersen_Graph dbr:P_versus_NP_problem dbr:Wagner's_theorem dbr:Word-representable_graph dbr:Minor-closed_graph_family dbr:Minor_(graph) dbr:Minor_(of_a_graph) dbr:Minor_of_a_graph |
| is foaf:primaryTopic of | wikipedia-en:Graph_minor |
