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!goblin1!goblin.stu.neva.ru!enother.net!peer01.iad.highwinds-media.com!
news.highwinds-media.com!feed-me.highwinds-media.com!post01.iad.highwinds-media
.com!fx30.iad.POSTED!not-for-mail
From: A.L. <a...@a...com>
Newsgroups: pl.comp.programming
Subject: Re: Grafy - eliminacja wierzcho?ków
Message-ID: <2...@4...com>
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>
<lp0k05$ldl$1@node2.news.atman.pl>
User-Agent: ForteAgent/7.00.32.1200
MIME-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: 8bit
Lines: 40
X-Complaints-To: a...@e...com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will
be unable to process your complaint properly.
Date: Wed, 02 Jul 2014 10:11:28 -0500
X-Received-Bytes: 2373
X-Received-Body-CRC: 64167340
Xref: news-archive.icm.edu.pl pl.comp.programming:206114
[ ukryj nagłówki ]
On Wed, 02 Jul 2014 11:39:16 +0200, bartekltg <b...@g...com>
wrote:

>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ą'.

Jedyna rozsadna definicja ktora spotkalem to taka:

Zbor wierzholkow I grafu G jezt sbiorem niezaleznym, jezeli podgraf
G(I) indukowany pzrez te wiercholki nie zawiera krawedzi.

Oczywiscie, wtedy pojedynczy wierzcholek tez jest zbiorem niezaleznym.

Ale 99.99% definicji mowi o "parach" i "przyleganiu"

A.L.