On 02.07.2014 05:14, A.L. wrote:
> On Wed, 02 Jul 2014 00:07:31 +0200, bartekltg <b...@g...com>
> wrote:
>
>> "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
>>
>>
>
>> "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""
>
> Ta definicja jest porabana, bo mowa jest o DWOCH wierzcholkach i
> krawedzi. Jak dla mnie zupelnie nie wynika co bedzie z JEDNYM
> wierzcholkiem.

Sformułowanie rzeczywiście nieszczęśliwe, ale czytelne.
Lepsze IMHO byłoby 'żadne dwa wierzchołki zbioru niezależnego
nie są połączone krawędzią'.

I to pokrywa przypadek jednego wierzchołka.

Dla purystów należałoby na początku ndadać, że rozważamy graf
nieskierowany bez pętli (cykli długości 1).


>
> Inne definicje tez takei sa
>
> Denition 1 Given an undirected graph G = (V;E) a subset of nodes S 
> V is an independent set (stable set) i there is no edge in E between
> any two nodes in S. A subset of nodes S is a clique if every pair of
> nodes in S have an edge between them in G.
>
> "Any two nodes" tez nie nasuwa watpliwosci ze musza byc co najmniej
> DWA wierzcholki
>
> Inna definicja:
>
> An independent set S of G is a set of vertices such that no unordered
> pair of vertices in S is an edge

To taż mi się nie podoba, nawet bardziej,
"para wierzchołków jest krawędzią".
"Jest połączona krawędzią" byłoby lepiej. Ale nadal jest to czytelne.

>
> Prosze o definicje ktora EXPLICITE stwierdzi co sie dzeje dla JEDNEGO
> wierzcholka. Jak dla mnie, nie jest to oczywiste


W zbiorze jednoelementowym istnieje para, która spełnia jakiś tam warunek?
Oczywiście NIE.
Skoro definicja nie wyklucza przypadku zbioru pustego (wiele tak robi,
gdy potrzeba) to całość jest spełniona.



pzdr
bartekltg