Maximal independent set (original) (raw)
In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property. A MIS is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so MISs are also called independent dominating sets. Two algorithmic problems are associated with MISs: and .
| Property | Value |
|---|---|
| dbo:abstract | In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property. For example, in the graph P3, a path with three vertices a, b, and c, and two edges ab and bc, the sets {b} and {a, c} are both maximally independent. The set {a} is independent, but is not maximal independent, because it is a subset of the larger independent set {a, c}. In this same graph, the maximal cliques are the sets {a, b} and {b, c}. A MIS is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so MISs are also called independent dominating sets. A graph may have many MISs of widely varying sizes; the largest, or possibly several equally large, MISs of a graph is called a maximum independent set. The graphs in which all maximal independent sets have the same size are called well-covered graphs. The phrase "maximal independent set" is also used to describe maximal subsets of independent elements in mathematical structures other than graphs, and in particular in vector spaces and matroids. Two algorithmic problems are associated with MISs: and . (en) Nella teoria dei grafi, un insieme indipendente massimale o insieme stabile massimale è un insieme indipendente che non è un sottoinsieme di nessun altro insieme indipendente. Cioè, è un insieme S tale che ogni spigolo del grafo ha almeno un estremo non in S e ogni vertice non in S ha almeno un vicino in S. Un insieme indipendente massimale è anche un nel grafo, e ogni insieme dominante che è indipendente deve essere indipendente massimale, così gli insiemi massimali indipendenti sono chiamati anche insiemi dominanti indipendenti. Un grafo può avere molti insiemi indipendenti massimali di dimensioni ampiamente variabili; un insieme indipendente massimale più grande è chiamato insieme indipendente massimo. Per esempio, nel grafo P3, un cammino con tre vertici a, b e c e due spigoli ab e bc, gli insiemi {b} e {a,c} sono entrambi massimamente indipendenti. L'insieme {a} è indipendente, ma non è massimamente indipendente, perché è un sottoinsieme dell'insieme indipendente più grande {a,c}. In questo stesso grafo, le cricche massimali sono gli insiemi {a,b} e {b,c}. La locuzione "insieme indipendente massimale" si usa anche per descrivere sottoinsiemi massimali di elementi indipendenti in strutture matematiche diverse dai grafi, e in particolare negli spazi vettoriali e nei matroidi. (it) В теории графов максимальным независимым множеством, максимальным устойчивым множеством, или максимальным стабильным множеством называется независимое множество, не являющееся подмножеством другого независимого множества. То есть это такое множество вершин S, что любое ребро графа имеет хотя бы одну конечную вершину, не принадлежащую S, и любая вершина не из S имеет хотя бы одну соседнюю в S. Максимальное независимое множество является также доминирующим в графе, а любое доминирующее множество, являющееся независимым, должно быть максимальным независимым, поэтому максимальные независимые множества также называют независимыми доминирующими множествами. Граф может иметь много максимальных независимых множеств в широком диапазоне размеров. Самое большое по размеру максимальное независимое множество называется наибольшим независимым множеством. Например, в графе P3, пути с тремя вершинами a, b и c и двумя рёбрами ab и bc, множества {b} и {a,c} оба являются максимальными независимыми, из них только {a,c} является наибольшим независимым. Множество {a} независимо, но не максимальное, поскольку является подмножеством {a,c}. В этом же графе максимальными кликами являются множества {a,b} и {b,c}. Словосочетание «максимальное независимое множество» употребляется также для описания максимальных подмножеств независимых элементов в математических структурах, отличных от графов, в частности, в векторных пространствах и матроидах. (ru) Максимальна незалежна множина або максмальна стабільна множина — незалежна множина, яка не є підмножиною будь-якої іншої незалежної множини. Тобто, це множина S така, що кожне ребро графа має один кінець не в S і кожна вершина не з S має щонайменше одного сусіда в S. Максимальна незалежна множина також є домінівною множиною графа, і кожна домінівна множина, що також незалежна повинна бути максимальною незалежною, отже максимальні незалежні множини також називають незалежними домінівними множинами. Граф може мати багато максимальних множин дуже відмінних розмірів; a якнайбільшу з максимальних незалежних множин називають найбільшою незалежною множиною. Наприклад, у графі P3, шлях з трьох вершин a, b і c і двох ребер ab і bc, обидві множини {b} і {a,c} максимальні незалежні. Множина {a} незалежна, але не максимальна, бо це підмножина більшої незалежної множини {a,c}. У цьому ж графі, максимальні кліки це множини {a,b} і {b,c}. Фраза «максимальна незалежна множина» також використовується для опису максимальних підмножин незалежних елементів не тільки в графах, зокрема у векторних просторах і матроїдах. (uk) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Cube-maximal-independence.svg?width=300 |
| dbo:wikiPageExternalLink | https://cs.uwaterloo.ca/journals/JIS/VOL11/Marichal/marichal.html https://pure.tue.nl/ws/files/2499168/Metis196442.pdf https://semanticscholar.org/paper/0d19245a27bc65a87a8014d5b8a66fb514c8ff0b http://www.cs.brown.edu/publications/jgaa/accepted/2003/Eppstein2003.7.2.pdf http://portal.acm.org/citation.cfm%3Fid=644182%7C |
| dbo:wikiPageID | 1793590 (xsd:integer) |
| dbo:wikiPageInterLanguageLink | dbpedia-de:Stabile_Menge |
| dbo:wikiPageLength | 39393 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1097443944 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Power_of_three dbr:Path_graph dbr:Vector_space dbr:Vertex_cover dbr:Vertex_cover_problem dbr:Independent_set_(graph_theory) dbr:Induced_subgraph dbc:Graph_theory_objects dbr:Complement_(set_theory) dbr:Complete_graph dbr:Matching_(graph_theory) dbr:Matrix_multiplication dbr:Clique_problem dbr:NC_(complexity) dbr:Complement_graph dbr:Computer_cluster dbr:Padovan_sequence dbr:Parallel_algorithm dbr:Path_(graph_theory) dbr:Perrin_number dbr:Theoretical_Computer_Science_(journal) dbr:Matroid dbr:Triangle-free_graph dbr:Well-covered_graph dbr:Distributed_algorithm dbr:P-complete dbr:Cycle_graph dbr:Parallel_random-access_machine dbr:Graph_theory dbr:Hard_spheres dbr:Israel_Journal_of_Mathematics dbr:Journal_of_Graph_Algorithms_and_Applications dbr:2-satisfiability dbr:Interval_graph dbr:Statistical_mechanics dbr:Chordal_graph dbr:Big_O_notation dbr:Bipartite_graph dbc:Computational_problems_in_graph_theory dbr:Cograph dbr:Dominating_set dbr:Planar_graph dbr:Plastic_number dbr:Vertex_(graph_theory) dbr:With_high_probability dbr:Set_packing dbr:Subset dbr:Turán_graph dbr:Maximum_independent_set dbr:Babeş-Bolyai_University dbr:Algorithmic_problem dbr:Complement_(graph_theory) dbr:Sparse_graph dbr:File:Cube-maximal-independence.svg dbr:File:Mis_pathgraph_p3.png dbr:File:Mis_related_sets.png dbr:File:Mis_stargraph_s8.png |
| dbp:wikiPageUsesTemplate | dbt:About dbt:Citation dbt:Cite_conference dbt:Efn dbt:Further dbt:Harvtxt dbt:ISBN dbt:Math dbt:Mvar dbt:Notelist dbt:Overline dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description dbt:Sub |
| dct:subject | dbc:Graph_theory_objects dbc:Computational_problems_in_graph_theory |
| rdf:type | yago:WikicatComputationalProblemsInGraphTheory yago:Abstraction100002137 yago:Attribute100024264 yago:Condition113920835 yago:Difficulty114408086 yago:Problem114410605 yago:State100024720 |
| rdfs:comment | In graph theory, a maximal independent set (MIS) or maximal stable set is an independent set that is not a subset of any other independent set. In other words, there is no vertex outside the independent set that may join it because it is maximal with respect to the independent set property. A MIS is also a dominating set in the graph, and every dominating set that is independent must be maximal independent, so MISs are also called independent dominating sets. Two algorithmic problems are associated with MISs: and . (en) Nella teoria dei grafi, un insieme indipendente massimale o insieme stabile massimale è un insieme indipendente che non è un sottoinsieme di nessun altro insieme indipendente. Cioè, è un insieme S tale che ogni spigolo del grafo ha almeno un estremo non in S e ogni vertice non in S ha almeno un vicino in S. Un insieme indipendente massimale è anche un nel grafo, e ogni insieme dominante che è indipendente deve essere indipendente massimale, così gli insiemi massimali indipendenti sono chiamati anche insiemi dominanti indipendenti. Un grafo può avere molti insiemi indipendenti massimali di dimensioni ampiamente variabili; un insieme indipendente massimale più grande è chiamato insieme indipendente massimo. (it) В теории графов максимальным независимым множеством, максимальным устойчивым множеством, или максимальным стабильным множеством называется независимое множество, не являющееся подмножеством другого независимого множества. То есть это такое множество вершин S, что любое ребро графа имеет хотя бы одну конечную вершину, не принадлежащую S, и любая вершина не из S имеет хотя бы одну соседнюю в S. Максимальное независимое множество является также доминирующим в графе, а любое доминирующее множество, являющееся независимым, должно быть максимальным независимым, поэтому максимальные независимые множества также называют независимыми доминирующими множествами. Граф может иметь много максимальных независимых множеств в широком диапазоне размеров. (ru) Максимальна незалежна множина або максмальна стабільна множина — незалежна множина, яка не є підмножиною будь-якої іншої незалежної множини. Тобто, це множина S така, що кожне ребро графа має один кінець не в S і кожна вершина не з S має щонайменше одного сусіда в S. Максимальна незалежна множина також є домінівною множиною графа, і кожна домінівна множина, що також незалежна повинна бути максимальною незалежною, отже максимальні незалежні множини також називають незалежними домінівними множинами. Граф може мати багато максимальних множин дуже відмінних розмірів; a якнайбільшу з максимальних незалежних множин називають найбільшою незалежною множиною. (uk) |
| rdfs:label | Maximale stabile Menge (de) Insieme indipendente massimale (it) Maximal independent set (en) Максимальное независимое множество (ru) Максимальна незалежна множина (uk) |
| owl:sameAs | freebase:Maximal independent set yago-res:Maximal independent set wikidata:Maximal independent set dbpedia-de:Maximal independent set dbpedia-hu:Maximal independent set dbpedia-it:Maximal independent set dbpedia-ru:Maximal independent set dbpedia-uk:Maximal independent set https://global.dbpedia.org/id/4wgwF |
| prov:wasDerivedFrom | wikipedia-en:Maximal_independent_set?oldid=1097443944&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Cube-maximal-independence.svg wiki-commons:Special:FilePath/Mis_pathgraph_p3.png wiki-commons:Special:FilePath/Mis_related_sets.png wiki-commons:Special:FilePath/Mis_stargraph_s8.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Maximal_independent_set |
| is dbo:wikiPageDisambiguates of | dbr:MIS |
| is dbo:wikiPageRedirects of | dbr:Minimal_vertex_cover dbr:Minimum_independent_dominating_set dbr:Minimum_maximal_independent_set dbr:Minimum_maximal_indepent_set |
| is dbo:wikiPageWikiLink of | dbr:Power_of_three dbr:Rook's_graph dbr:Pentagonal_bipyramid dbr:Dedekind–MacNeille_completion dbr:Dürer_graph dbr:Independent_set_(graph_theory) dbr:Generalized_Petersen_graph dbr:Union-closed_sets_conjecture dbr:Cluster_graph dbr:Graph_coloring dbr:Snub_disphenoid dbr:Clique_(graph_theory) dbr:Perrin_number dbr:Triangle-free_graph dbr:Domatic_number dbr:Three_utilities_problem dbr:277_(number) dbr:Dijkstra_Prize dbr:Cograph dbr:Recursive_largest_first_algorithm dbr:Dominating_set dbr:Greedy_coloring dbr:Minimal_vertex_cover dbr:Octahedron dbr:MIS dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Michael_Luby dbr:Reverse-search_algorithm dbr:Minimum_independent_dominating_set dbr:Minimum_maximal_independent_set dbr:Minimum_maximal_indepent_set |
| is foaf:primaryTopic of | wikipedia-en:Maximal_independent_set |
