Re: Grafy - eliminacja wierzcho?ków - Grupy dyskusyjne w eGospodarka.pl

eGospodarka.pl › Grupy › pl.comp.programming › Grafy - eliminacja wierzchołków › Re: Grafy - eliminacja wierzcho?ków

Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!.POSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: Grafy - eliminacja wierzcho?ków
Date: Wed, 02 Jul 2014 11:39:16 +0200
Organization: ATMAN - ATM S.A.
Lines: 77
Message-ID: <lp0k05$ldl$1@node2.news.atman.pl>
References: <louf2u$njl$1@node1.news.atman.pl> <louokg$ohi$1@node2.news.atman.pl>
<g...@4...com>
<lov10q$1ad$1@node2.news.atman.pl>
<8...@4...com>
<lovbf3$chn$1@node2.news.atman.pl>
<u...@4...com>
NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node2.news.atman.pl 1404293957 21941 89.73.81.145 (2 Jul 2014 09:39:17 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Wed, 2 Jul 2014 09:39:17 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101
Thunderbird/24.6.0
In-Reply-To: <u...@4...com>
Xref: news-archive.icm.edu.pl pl.comp.programming:206109
[ ukryj nagłówki ]
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
>
> Denition 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