On 01.07.2014 23:50, A.L. wrote:
> On Tue, 01 Jul 2014 21:09:14 +0200, bartekltg <b...@g...com>
> wrote:
>
>> On 01.07.2014 20:59, A.L. wrote:
>>> On Tue, 01 Jul 2014 18:46:08 +0200, bartekltg <b...@g...com>
>>
>> ****
>>
>>>>> Nowy problem:
>>>>> - nie można eliminować krawędzi gdy nie eliminujemy wierzchołków
>>>>> - eliminując wierzchołek, eliminujemy krawędzie połączone z tym
>>>>> wierzchołkiem
>>>>> Chodzi o to, aby wyeliminować najmniejszą możliwą liczbę wierzchołków,
>>>>> aby wszystkie pozostałe były samotne i nie było żadnej krawędzi w grafie.
>>
>> ****
>>
>>>> Problem rzeczywiście ma nazwę i jest jako tako rozpoznany.
>>>>
>>>> http://en.wikipedia.org/wiki/Maximum_independent_set
#Finding_maximum_independent_sets
>>>>
>>>> Na zachętę, problem NP-trudny;-)
>>
>>
>>> To jest inny problem niz postawiony pzrez OP. OP chce eliminowac
>>> wierzcholki, ten problem jak wyzej niczego nie eliminuje. W tym
>>> problemie, dla DANEGO grafu poszukuje sie wierzcholkow nie polaczonych
>>> krawedzia
>>
>> Przeczytaj to raz jeszcze. To dokładnie ten sam problem.
>> Dla danego grafu wyznaczasz zbiór niezależny i wyrzucasz wszystkie
>> wierzchołki do niego nie należące, wydawało mi się, że to oczywiste
>> uzupełnienie.
>
> A jezel zbior niezalezny jest pusty ("complete graph")?
>
> Byc moze cegos nie rozumiem z problemu OP.
>
> Zalozmy graf A-B, B-C, C-A, eliminujemy A a wiec krawedzie A-C, A-B,
> zostaje B-C,. wiec eliminujemy B i zostaje C. Tego sie nie dostanie
> twoim sposobem, bo zbior niezalezny grafu A-B-C jest pusty.
>
> Byc moze OP powinien byc bardziej precyzyjny. Bardziej uwazne czytanie
> postu OP nic nie da, przynakmniej ja nie moge nic wyczytac

Wątkodawce rozumiesz dobrze, musiałeś coś przeoczyć w definicji
zbioru niezależnego.

Pojedynczy wierzchołek w grafie pełnym _jest_ zbiorem niezależnym.

Spójrz raz jeszcze na definicję:

"[...] an independent set [...] is a set of vertices in a graph,
no two of which are adjacent. That is, it is a set I of vertices
such that for every two vertices in I, there is no edge connecting
the two. Equivalently, each edge in the graph has at most one
endpoint in I. " //wiki en

"W teorii grafów zbiór niezależny w grafie G=(V,E), to zbiór
wierzchołków V' \subseteq V, pomiędzy którymi nie ma żadnej krawędzi.
Innymi słowy każda krawędź w G jest incydentna z co najwyżej jednym
wierzchołkiem w tym zbiorze."//wiki pl

"An independent vertex set of a graph G is a subset of the vertices
such that no two vertices in the subset represent an edge of G"
// http://mathworld.wolfram.com/IndependentVertexSet.ht
ml

Pojedynczy wierzchołek siłą rzeczy zawsze jest zbiorem niezależnym
(choć niekoniecznie największym czy maksymalnym).

pzdr
bartekltg