Multipartite graph (original) (raw)
Ein -partiter Graph ist in der Graphentheorie ein einfacher Graph, dessen Knotenmenge in k disjunkte Teilmengen zerfällt, sodass die Knoten jeder dieser Teilmengen untereinander nicht benachbart sind. Für heißen diese Graphen bipartite Graphen.
| Property | Value |
|---|---|
| dbo:abstract | Ein -partiter Graph ist in der Graphentheorie ein einfacher Graph, dessen Knotenmenge in k disjunkte Teilmengen zerfällt, sodass die Knoten jeder dieser Teilmengen untereinander nicht benachbart sind. Für heißen diese Graphen bipartite Graphen. (de) In graph theory, a part of mathematics, a k-partite graph is a graph whose vertices are (or can be) partitioned into k different independent sets. Equivalently, it is a graph that can be colored with k colors, so that no two endpoints of an edge have the same color. When k = 2 these are the bipartite graphs, and when k = 3 they are called the tripartite graphs. Bipartite graphs may be recognized in polynomial time but, for any k > 2 it is NP-complete, given an uncolored graph, to test whether it is k-partite.However, in some applications of graph theory, a k-partite graph may be given as input to a computation with its coloring already determined; this can happen when the sets of vertices in the graph represent different types of objects. For instance, folksonomies have been modeled mathematically by tripartite graphs in which the three sets of vertices in the graph represent users of a system, resources that the users are tagging, and tags that the users have applied to the resources. A complete k-partite graph is a k-partite graph in which there is an edge between every pair of vertices from different independent sets. These graphs are described by notation with a capital letter K subscripted by a sequence of the sizes of each set in the partition. For instance, K2,2,2 is the complete tripartite graph of a regular octahedron, which can be partitioned into three independent sets each consisting of two opposite vertices. A complete multipartite graph is a graph that is complete k-partite for some k.The Turán graphs are the special case of complete multipartite graphs in which each two independent sets differ in size by at most one vertex.Complete k-partite graphs, complete multipartite graphs, and their complement graphs, the cluster graphs, are special cases of cographs, and can be recognized in polynomial time even when the partition is not supplied as part of the input. (en) Graf k-dzielny – naturalne rozszerzenie klasy grafów dwudzielnych - jest to graf, którego zbiór wierzchołków można podzielić na k parami rozłącznych podzbiorów takich, że żadne dwa węzły należące do tego samego zbioru nie są połączone krawędzią. Innymi słowy, jeżeli jest grafem k-dzielnym, to na zbiorze jego wierzchołków istnieje : taki, że (pl) k-дольный граф — граф, множество вершин которого можно разбить на k независимых множеств (доль). Эквивалентно, это граф, который можно раскрасить с помощью k цветов так, что концы любого выбранного ребра будут окрашены в разные цвета. При k = 2 k-дольный граф называется двудольным. Распознавание двудольных графов может быть выполнено за полиномиальное время, но для любого k > 2 задача определения, является ли данный неокрашенный граф k-дольным, становится NP-полной.Впрочем, в некоторых приложениях теории графов k-дольный граф может быть задан на входе уже раскрашенным; это может случиться, когда множества вершин графа соответствуют разным типам объектов. Например, фолксономии математически моделировались трёхдольными графами, в которых три множества вершин соответствуют пользователям системы, ресурсам, которые подлежат пометке тегами, и собственно тегам Полный k-дольный граф — это k-дольный граф, такой, что любые две вершины, входящие в разные доли, смежны. Полный k-дольный граф может быть описан нотацией где — числа вершин в долях графа. Например, — полный трёхдольный граф правильного октаэдра, состоящий из трёх независимых множеств, каждое из которых включает в себя две противоположные вершины октаэдра. Полный многодольный граф — это граф, который является полным k-дольным для некоторого k. Граф Турана — полный многодольный граф, мощности любых двух доль которого отличаются не более чем на 1. Полные многодольные графы — частный случай кографов. (ru) 在數學的分支圖論中，一個 k-分圖是一個图，其點集被分成 k 部分，各部分各自形成独立集。換句话說，可以把圖的所有點著色，使得相鄰的點著不同色且總共用了k 個顏色。k = 2 的情況被稱作二分圖，而 k = 3 的情況被稱作三分圖。 事實上，辨別一個圖是二分圖只需要多項式時間。但當 k > 2，辨別一個圖是否為 k-分圖卻是NP完全的 。不過，在一些圖論的應用場合中，給計算器處理 k-分圖會包含 k 個部份的劃分，比如說各個部分所代表的是不同類型的物件。例如可以用三分圖做大眾分類法的數學模型，三個部份分別為系統的使用者、系統擁有的資料來源、使用者給資料來源的標籤。 一個完全 k-分圖是一個 k-分圖，其中兩點若屬於相異的部分則必相鄰。該圖的記為一個大寫 K，在下標標註個部份的頂點數，並用英文逗號分開。例如 K2,2,2 可以想成正八面體的頂點和邊，其中三個獨立集使三組對頂點。所有的完全 k-分圖統稱為完全多分圖。是一種特殊的完全多分圖，其中各部分的頂點數至多差 1。 (zh) k-частковий граф — граф, множину вершин якого можна розбити на k незалежних множин (часток). Еквівалентно, це граф, який можна розфарбувати за допомогою k кольорів так, що кінці будь-якого ребра будуть пофарбовані в різні кольори. При k = 2 k-частковий граф називається двочастковим. Розпізнати двочастковий граф можна за поліноміальний час, але для будь-якого k > 2 задача визначення, чи є даний нерозфарбований граф k-частковим, стає NP-повною. Втім, у деяких застосуваннях теорії графів k-частковий граф можна задати на вході вже розфарбованим; це може статися, коли множини вершин графу відповідають різним типам об'єктів. Наприклад, фолксономії математично моделювалися тричастковими графами, в яких три множини вершин відповідають користувачам системи, ресурсам, які позначаються тегами, і власне тегам Повний k-частковий граф — це k-частковий граф, такий, що будь-які дві вершини, які належать до різних часток, суміжні. Повний k-частковий граф можна описати нотацією де — число вершин у частках графу. Наприклад, — повний тричастковий граф правильного октаедра, що складається з трьох незалежних множин, кожна з яких включає дві протилежні вершини октаедра. Повний багаточастковий граф — це граф, який є повним k-частковим для деякого k. Граф Турана — повний багаточастковий граф, потужності будь-яких двох часток якого відрізняються не більше ніж на 1. Повні багаточасткові графи — частковий випадок кографів. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Complex_tripartite_graph_octahedron.svg?width=300 |
| dbo:wikiPageID | 39469099 (xsd:integer) |
| dbo:wikiPageLength | 4080 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1096395087 (xsd:integer) |
| dbo:wikiPageWikiLink | dbc:Graph_families dbr:Independent_set_(graph_theory) dbr:16-cell dbr:Cross-polytope dbr:Cluster_graph dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:NP-complete dbr:Regular_octahedron dbr:Complement_graph dbr:Folksonomy dbr:Graph_partition dbr:Graph_theory dbr:Bipartite_graph dbr:Cograph dbr:Polynomial_time dbr:Octahedron dbr:Vertex_(graph_theory) dbr:Turán_graph dbr:File:3-generalized-3-orthoplex-tripartite.svg dbr:File:Complex_multipartite_graph_16-cell.svg dbr:File:Complex_tripartite_graph_octahedron.svg |
| dbp:wikiPageUsesTemplate | dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Sub |
| dct:subject | dbc:Graph_families |
| gold:hypernym | dbr:Graph |
| rdf:type | dbo:Software yago:Abstraction100002137 yago:Family108078020 yago:Group100031264 yago:Organization108008335 yago:WikicatGraphFamilies yago:YagoLegalActor yago:YagoLegalActorGeo yago:YagoPermanentlyLocatedEntity yago:SocialGroup107950920 yago:Unit108189659 |
| rdfs:comment | Ein -partiter Graph ist in der Graphentheorie ein einfacher Graph, dessen Knotenmenge in k disjunkte Teilmengen zerfällt, sodass die Knoten jeder dieser Teilmengen untereinander nicht benachbart sind. Für heißen diese Graphen bipartite Graphen. (de) Graf k-dzielny – naturalne rozszerzenie klasy grafów dwudzielnych - jest to graf, którego zbiór wierzchołków można podzielić na k parami rozłącznych podzbiorów takich, że żadne dwa węzły należące do tego samego zbioru nie są połączone krawędzią. Innymi słowy, jeżeli jest grafem k-dzielnym, to na zbiorze jego wierzchołków istnieje : taki, że (pl) 在數學的分支圖論中，一個 k-分圖是一個图，其點集被分成 k 部分，各部分各自形成独立集。換句话說，可以把圖的所有點著色，使得相鄰的點著不同色且總共用了k 個顏色。k = 2 的情況被稱作二分圖，而 k = 3 的情況被稱作三分圖。 事實上，辨別一個圖是二分圖只需要多項式時間。但當 k > 2，辨別一個圖是否為 k-分圖卻是NP完全的 。不過，在一些圖論的應用場合中，給計算器處理 k-分圖會包含 k 個部份的劃分，比如說各個部分所代表的是不同類型的物件。例如可以用三分圖做大眾分類法的數學模型，三個部份分別為系統的使用者、系統擁有的資料來源、使用者給資料來源的標籤。 一個完全 k-分圖是一個 k-分圖，其中兩點若屬於相異的部分則必相鄰。該圖的記為一個大寫 K，在下標標註個部份的頂點數，並用英文逗號分開。例如 K2,2,2 可以想成正八面體的頂點和邊，其中三個獨立集使三組對頂點。所有的完全 k-分圖統稱為完全多分圖。是一種特殊的完全多分圖，其中各部分的頂點數至多差 1。 (zh) In graph theory, a part of mathematics, a k-partite graph is a graph whose vertices are (or can be) partitioned into k different independent sets. Equivalently, it is a graph that can be colored with k colors, so that no two endpoints of an edge have the same color. When k = 2 these are the bipartite graphs, and when k = 3 they are called the tripartite graphs. (en) k-дольный граф — граф, множество вершин которого можно разбить на k независимых множеств (доль). Эквивалентно, это граф, который можно раскрасить с помощью k цветов так, что концы любого выбранного ребра будут окрашены в разные цвета. При k = 2 k-дольный граф называется двудольным. Полный k-дольный граф — это k-дольный граф, такой, что любые две вершины, входящие в разные доли, смежны. Полный k-дольный граф может быть описан нотацией Граф Турана — полный многодольный граф, мощности любых двух доль которого отличаются не более чем на 1. Полные многодольные графы — частный случай кографов. (ru) k-частковий граф — граф, множину вершин якого можна розбити на k незалежних множин (часток). Еквівалентно, це граф, який можна розфарбувати за допомогою k кольорів так, що кінці будь-якого ребра будуть пофарбовані в різні кольори. При k = 2 k-частковий граф називається двочастковим. Повний k-частковий граф — це k-частковий граф, такий, що будь-які дві вершини, які належать до різних часток, суміжні. Повний k-частковий граф можна описати нотацією (uk) |
| rdfs:label | K-partiter Graph (de) Multipartite graph (en) Graf k-dzielny (pl) Многодольный граф (ru) 多分圖 (zh) Багаточастковий граф (uk) |
| owl:sameAs | freebase:Multipartite graph yago-res:Multipartite graph wikidata:Multipartite graph dbpedia-de:Multipartite graph dbpedia-hu:Multipartite graph dbpedia-pl:Multipartite graph dbpedia-ru:Multipartite graph dbpedia-sr:Multipartite graph dbpedia-uk:Multipartite graph dbpedia-zh:Multipartite graph https://global.dbpedia.org/id/g6Ly |
| prov:wasDerivedFrom | wikipedia-en:Multipartite_graph?oldid=1096395087&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/3-generalized-3-orthoplex-tripartite.svg wiki-commons:Special:FilePath/Complex_multipartite_graph_16-cell.svg wiki-commons:Special:FilePath/Complex_tripartite_graph_octahedron.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Multipartite_graph |
| is dbo:wikiPageRedirects of | dbr:Tripartite_graphs_and_networks dbr:Complete_multipartite_graph dbr:K-partite_graph dbr:Tripartite_graph |
| is dbo:wikiPageWikiLink of | dbr:Multidimensional_network dbr:Cluster_graph dbr:Graph_coloring dbr:Forbidden_subgraph_problem dbr:Graph_entropy dbr:Bipartite_graph dbr:Incidence_structure dbr:Strongly_regular_graph dbr:Turán's_theorem dbr:Multidimensional_assignment_problem dbr:P_versus_NP_problem dbr:Thagomizer dbr:Tripartite_graphs_and_networks dbr:Complete_multipartite_graph dbr:K-partite_graph dbr:Tripartite_graph |
| is foaf:primaryTopic of | wikipedia-en:Multipartite_graph |
