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