| dbo:abstract
|
- في نظرية الرسم البياني، نعرف مجموعة مستقلة أومجموعة مستقرة (stable set أو independent set) بأنها مجموعة من رؤوس والتي كل رأسين بها هما غير متجاوران. بمعنى آخر، المجموعة المستقلة هي مجموعة S من الرؤوس بحيث لا يوجد ضلع يربط بين كل رأسين في S. وهذا يعني أن كل ضلع في الرسم البياني له رأس واحد عالأكثر واحدة على الأكثر في S. حجم المجموعة المستقلة هو عدد الرؤوس بها. تسمى المجموعات المستقلة أيضا بمجموعات مستقرة داخليا. المجموعة المستقلة القصوى (maximal independent set ) هي إما مجموعة مستقلة بحيث أن إضافة أي رأس لها ينتج عنه ضلع ينتمي بالكامل لهذه المجموعة أو مجموعة من جميع رؤوس الرسم البياني الخالي (أي لايحتوي على أضلاع). تعرف المجموعة المستقلة القصوى بشكل آخر بأنها مجموعة مستقلة والتي لها أكبر حجم ممكن للرسم البياني G المحدد. يُسمى هذا الرقم بعدد الاستقلال (independence) لـ G ، ويرمز بالرمز . تعتبر مسألة إيجاد المجموعة المستقلة القصوى مشكلة من النوع NP-hard بمسائل الأمثلية. فبالتالي فإنه من غير المحتمل وجود خوارزمية فعالة لإيجاد الحد الأقصى المستقل لمجموعة من الرسم البياني. كل مجموعة مستقلة قصوى هي أيضًا الحد الأقصى، لكن العكس ليس دائما صحيح. (ar)
- Nezávislá množina (NM) je pojem z teorie grafů. Nezávislá množina v grafu je taková množina jeho vrcholů, že žádné dva z nich nejsou spojeny hranou. (cs)
- Eine stabile Menge, unabhängige Menge oder Co-Clique ist in der Graphentheorie eine Teilmenge von Knoten eines Graphen, die zueinander nicht adjazent sind. Zu entscheiden, ob ein Graph eine stabile Menge einer bestimmten Mindestgröße enthält, wird Stabilitätsproblem genannt und gilt, wie das Finden einer größten stabilen Menge, als algorithmisch schwierig. (de)
- En teoría de grafos, un conjunto independiente o estable es un conjunto de vértices en un grafo tal que ninguno de sus vértices es adyacente a otro. Es decir, es un conjunto V de vértices tal que para ningún par de ellos existe alguna arista que los conecten. En otras palabras, cada arista en el grafo contiene a lo más un vértice en V. El tamaño de un conjunto independiente es el número de vértices que contiene. Un es un conjunto independiente tal que añadiendo cualquier otro vértice al conjunto, este deja de ser independiente. (es)
- In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. A maximal independent set is an independent set that is not a proper subset of any other independent set. A maximum independent set is an independent set of largest possible size for a given graph . This size is called the independence number of and is usually denoted by . The optimization problem of finding such a set is called the maximum independent set problem. It is a strongly NP-hard problem. As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph. Every maximum independent set also is maximal, but the converse implication does not necessarily hold. (en)
- Dalam teori graf, himpunan bebas (bahasa Inggris: independent set) adalah serangkaian simpul (vertex) dalam graf, tidak ada dua yang berdekatan. Artinya, ada himpunan I dari simpul tersebut di mana untuk setiap dua simpul dalam I, tidak ada tepi yang menghubungkan keduanya. Hal ini Ekuivalen dengan pernyataan bahwa masing-masing sisi (edge) dalam grafik memiliki paling banyak satu titik akhir di I. (in)
- En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient. (fr)
- グラフ理論における独立集合（どくりつしゅうごう、英: independent set）または安定集合（英: stable set）は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。 (maximal independent set) とは、任意の他の頂点を追加するとその集合に辺の両端点が含まれてしまうような独立集合である。 最大独立集合 (maximum independent set) は与えられたグラフ G の最も大きな独立集合であり、その大きさを α(G) と表記する。このような集合を求める問題を最大独立集合問題と呼び、NP完全問題である。したがって、グラフの最大独立集合を求める効率的なアルゴリズムは存在が疑わしい。 与えられたグラフが特定の大きさの独立集合を持つかどうかを判定する問題を独立集合問題と呼ぶ。これは計算上、そのグラフが特定の大きさのクリークを持つかどうかの判定と等価である。このことは、グラフが大きさ k の独立集合を持つとき、その補グラフ（頂点は同じだが、辺が相補的なグラフ）は大きさ k のクリークを持つという事実から導かれる。独立集合（およびクリーク）の決定問題は、NP完全問題であることが知られている。 最大独立集合と極大独立集合は異なる概念である。極大独立集合は他のもっと大きな独立集合の部分集合とはならない。極大独立集合を求める問題は簡単な貪欲法で多項式時間で解くことができる。 (ja)
- 그래프 이론에서 독립 집합(獨立集合, 영어: independent set)은 서로 인접하지 않는 꼭짓점들의 집합이다. (ko)
- Nella teoria dei grafi, un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due. Cioè, è un insieme I di vertici tale che per ogni due vertici in I, non c'è nessuno spigolo che connette i due. Equivalentemente, ciascuno spigolo del grafo ha al massimo un estremo in I. La dimensione di un insieme indipendente è il numero di vertici che esso contiene. Gli insiemi indipendenti sono stati chiamati anche insiemi internamente stabili. Un insieme indipendente massimale è un insieme indipendente tale che aggiungere un qualsiasi vertice all'insieme costringe l'insieme stesso a contenere uno spigolo. Un insieme indipendente massimo è un insieme indipendente della più grande dimensione possibile per un dato grafo G. Questa dimensione è chiamata numero d'indipendenza di G, e denotata α(G). Il problema di trovare un tale insieme è chiamato problema del massimo insieme indipendente ed è un problema di ottimizzazione NP-difficile. Come tale, è improbabile che esista un algoritmo efficiente per trovare un insieme indipendente massimo di un grafo. Ogni massimo insieme indipendente è anche massimale, ma l'implicazione inversa non è necessariamente valida. (it)
- In de grafentheorie verstaat men onder onafhankelijke verzameling of stabiele verzameling (independent set in het Engels) van een graaf, een deelverzameling van de knopen van die graaf die twee aan twee niet verbonden zijn door een zijde. (nl)
- Na teoria dos grafos, um conjunto independente de um grafo é um conjunto de vértices de tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se e são vértices quaisquer de um conjunto independente, não há aresta entre e . Todo grafo tem ao menos um conjunto independente: o conjunto vazio. Um grafo pode ter vários conjuntos independentes distintos. Se S é um conjunto independente de G e não existe um conjunto independente de G maior que S, diz-se que S é um conjunto independente máximo de G. O problema de, dado um grafo G, determinar se há um conjunto independente de tamanho k é um problema NP-completo. (pt)
- Zbiór niezależny w grafie – zbiór wierzchołków pomiędzy którymi nie ma żadnej krawędzi. Innymi słowy każda krawędź w jest incydentna z co najwyżej jednym wierzchołkiem w tym zbiorze. Problem największego zbioru niezależnego polegający na znalezieniu w danym grafie zbioru niezależnego o maksymalnej liczbie wierzchołków, jest znanym problemem NP-trudnym. Problem ten nie powinien być mylony z maksymalnym zbiorem niezależnym w sensie inkluzji. Zbiór taki jest maksymalny gdy dodanie do niego jakiegokolwiek elementu sprawia że przestaje być niezależny. Znalezienie takiego zbioru wierzchołków jest proste i może być wykonane za pomocą algorytmu zachłannego.
* 9 zaznaczonych na niebiesko wierzchołków tworzy (zaskakująco asymetryczny) maksymalny zbiór niezależny w tym grafie o 24 wierzchołkach. (pl)
- En oberoende mängd är inom matematik, specifikt grafteori, en mängd av noder M i en graf G sådan att det inte finns någon båge i G mellan någon av noderna i M. Ekvivalent uttryckt så är mängden M oberoende om varje båge i G har högst en ändpunkt som ligger i M. Med storleken på en oberoende mängd avses antalet noder som mängden innehåller. En maximal oberoende mängd är en oberoende mängd sådan att om man lägger till en nod i mängden är den inte oberoende längre. En största oberoende mängd är en oberoende mängd sådan att det inte finns någon oberoende mängd som har fler noder. Storleken på en största oberoende mängd kallas grafens oberoendetal. Även när det gäller bågar i grafer talas det om oberoende mängder, dessa kallas vanligtvis matchningar. (sv)
- Независимое множество в теории графов может быть как независимым множеством вершин, так и независимым множеством рёбер. Независимые множества рассматриваются в задачах покрытия графов. (ru)
- 独立集（英语：Independent set）是图论中的概念。一个独立集（也称为稳定集）是一个图中一些两两不相邻的顶点所形成的集合。换句话说，独立集由图中若干顶点组成，且中任两个顶点之间没有边。等价地，图中的每条边至多有一个端点属于。一个独立集的基数是它包含顶点的数目。 如果往图的独立集中添加任一个顶点都会使独立性丧失（亦即造成某两点间有边），那么称是极大独立集。如果是图中所有独立集之中基数最大的，那么称是最大独立集，且将该基数称为的独立数，记为。一般来讲，图中可能存在多个极大独立集；最大独立集亦如是。最大独立集一定是极大独立集，但反之未必。 给定一张图，寻找其中一个最大独立集的问题被称为最大独立集问题。该问题已知是NP困难的最优化问题，且即便试图以常数倍近似也是NP困难的。因此，计算机科学家普遍相信不存在解决该问题的高效算法，无论是精确求解还是以常数倍近似求解。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 24863 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:title
|
- Maximal Independent Vertex Set (en)
|
| dbp:urlname
|
- MaximalIndependentVertexSet (en)
|
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- Nezávislá množina (NM) je pojem z teorie grafů. Nezávislá množina v grafu je taková množina jeho vrcholů, že žádné dva z nich nejsou spojeny hranou. (cs)
- Eine stabile Menge, unabhängige Menge oder Co-Clique ist in der Graphentheorie eine Teilmenge von Knoten eines Graphen, die zueinander nicht adjazent sind. Zu entscheiden, ob ein Graph eine stabile Menge einer bestimmten Mindestgröße enthält, wird Stabilitätsproblem genannt und gilt, wie das Finden einer größten stabilen Menge, als algorithmisch schwierig. (de)
- En teoría de grafos, un conjunto independiente o estable es un conjunto de vértices en un grafo tal que ninguno de sus vértices es adyacente a otro. Es decir, es un conjunto V de vértices tal que para ningún par de ellos existe alguna arista que los conecten. En otras palabras, cada arista en el grafo contiene a lo más un vértice en V. El tamaño de un conjunto independiente es el número de vértices que contiene. Un es un conjunto independiente tal que añadiendo cualquier otro vértice al conjunto, este deja de ser independiente. (es)
- Dalam teori graf, himpunan bebas (bahasa Inggris: independent set) adalah serangkaian simpul (vertex) dalam graf, tidak ada dua yang berdekatan. Artinya, ada himpunan I dari simpul tersebut di mana untuk setiap dua simpul dalam I, tidak ada tepi yang menghubungkan keduanya. Hal ini Ekuivalen dengan pernyataan bahwa masing-masing sisi (edge) dalam grafik memiliki paling banyak satu titik akhir di I. (in)
- En théorie des graphes, un stable – appelé aussi ensemble indépendant ou independent set en anglais – est un ensemble de sommets deux à deux non adjacents. La taille d'un stable est égale au nombre de sommets qu'il contient. (fr)
- 그래프 이론에서 독립 집합(獨立集合, 영어: independent set)은 서로 인접하지 않는 꼭짓점들의 집합이다. (ko)
- In de grafentheorie verstaat men onder onafhankelijke verzameling of stabiele verzameling (independent set in het Engels) van een graaf, een deelverzameling van de knopen van die graaf die twee aan twee niet verbonden zijn door een zijde. (nl)
- Независимое множество в теории графов может быть как независимым множеством вершин, так и независимым множеством рёбер. Независимые множества рассматриваются в задачах покрытия графов. (ru)
- 独立集（英语：Independent set）是图论中的概念。一个独立集（也称为稳定集）是一个图中一些两两不相邻的顶点所形成的集合。换句话说，独立集由图中若干顶点组成，且中任两个顶点之间没有边。等价地，图中的每条边至多有一个端点属于。一个独立集的基数是它包含顶点的数目。 如果往图的独立集中添加任一个顶点都会使独立性丧失（亦即造成某两点间有边），那么称是极大独立集。如果是图中所有独立集之中基数最大的，那么称是最大独立集，且将该基数称为的独立数，记为。一般来讲，图中可能存在多个极大独立集；最大独立集亦如是。最大独立集一定是极大独立集，但反之未必。 给定一张图，寻找其中一个最大独立集的问题被称为最大独立集问题。该问题已知是NP困难的最优化问题，且即便试图以常数倍近似也是NP困难的。因此，计算机科学家普遍相信不存在解决该问题的高效算法，无论是精确求解还是以常数倍近似求解。 (zh)
- في نظرية الرسم البياني، نعرف مجموعة مستقلة أومجموعة مستقرة (stable set أو independent set) بأنها مجموعة من رؤوس والتي كل رأسين بها هما غير متجاوران. بمعنى آخر، المجموعة المستقلة هي مجموعة S من الرؤوس بحيث لا يوجد ضلع يربط بين كل رأسين في S. وهذا يعني أن كل ضلع في الرسم البياني له رأس واحد عالأكثر واحدة على الأكثر في S. حجم المجموعة المستقلة هو عدد الرؤوس بها. تسمى المجموعات المستقلة أيضا بمجموعات مستقرة داخليا. كل مجموعة مستقلة قصوى هي أيضًا الحد الأقصى، لكن العكس ليس دائما صحيح. (ar)
- In graph theory, an independent set, stable set, coclique or anticlique is a set of vertices in a graph, no two of which are adjacent. That is, it is a set of vertices such that for every two vertices in , there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in . A set is independent if and only if it is a clique in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. (en)
- Nella teoria dei grafi, un insieme indipendente o insieme stabile è un insieme di vertici in un grafo, nessuno dei quali è adiacente a due a due. Cioè, è un insieme I di vertici tale che per ogni due vertici in I, non c'è nessuno spigolo che connette i due. Equivalentemente, ciascuno spigolo del grafo ha al massimo un estremo in I. La dimensione di un insieme indipendente è il numero di vertici che esso contiene. Gli insiemi indipendenti sono stati chiamati anche insiemi internamente stabili. (it)
- グラフ理論における独立集合（どくりつしゅうごう、英: independent set）または安定集合（英: stable set）は、1つのグラフ内で互いに隣接していない頂点の集合である。すなわち、頂点の集合 V で、V の任意の2つの頂点をつなぐ辺が存在しない場合をいう。等価的に、そのグラフの各辺の高々一方の端点のみが V の元である。独立集合の大きさとはその中の頂点の個数である。 (maximal independent set) とは、任意の他の頂点を追加するとその集合に辺の両端点が含まれてしまうような独立集合である。 最大独立集合 (maximum independent set) は与えられたグラフ G の最も大きな独立集合であり、その大きさを α(G) と表記する。このような集合を求める問題を最大独立集合問題と呼び、NP完全問題である。したがって、グラフの最大独立集合を求める効率的なアルゴリズムは存在が疑わしい。 最大独立集合と極大独立集合は異なる概念である。極大独立集合は他のもっと大きな独立集合の部分集合とはならない。極大独立集合を求める問題は簡単な貪欲法で多項式時間で解くことができる。 (ja)
- Zbiór niezależny w grafie – zbiór wierzchołków pomiędzy którymi nie ma żadnej krawędzi. Innymi słowy każda krawędź w jest incydentna z co najwyżej jednym wierzchołkiem w tym zbiorze. Problem największego zbioru niezależnego polegający na znalezieniu w danym grafie zbioru niezależnego o maksymalnej liczbie wierzchołków, jest znanym problemem NP-trudnym.
* 9 zaznaczonych na niebiesko wierzchołków tworzy (zaskakująco asymetryczny) maksymalny zbiór niezależny w tym grafie o 24 wierzchołkach. (pl)
- Na teoria dos grafos, um conjunto independente de um grafo é um conjunto de vértices de tal que não existem dois vértices adjacentes contidos em S. Em outras palavras, se e são vértices quaisquer de um conjunto independente, não há aresta entre e . Todo grafo tem ao menos um conjunto independente: o conjunto vazio. Um grafo pode ter vários conjuntos independentes distintos. (pt)
- En oberoende mängd är inom matematik, specifikt grafteori, en mängd av noder M i en graf G sådan att det inte finns någon båge i G mellan någon av noderna i M. Ekvivalent uttryckt så är mängden M oberoende om varje båge i G har högst en ändpunkt som ligger i M. Med storleken på en oberoende mängd avses antalet noder som mängden innehåller. Även när det gäller bågar i grafer talas det om oberoende mängder, dessa kallas vanligtvis matchningar. (sv)
|
| rdfs:label
|
- مجموعة مستقلة (نظرية الرسومات) (ar)
- Nezávislá množina (cs)
- Stabile Menge (de)
- Conjunto independiente (es)
- Himpunan bebas (teori graf) (in)
- Stable (théorie des graphes) (fr)
- Independent set (graph theory) (en)
- Insieme indipendente (teoria dei grafi) (it)
- 독립집합 (ko)
- 独立集合 (ja)
- Onafhankelijke verzameling (nl)
- Zbiór niezależny (pl)
- Conjunto independente (pt)
- Независимое множество (ru)
- Oberoende mängd (sv)
- 独立集 (zh)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
