| 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)
|
| 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)
|
