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.

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

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

A.L.

do góry

On Wed, 02 Jul 2014 00:07:31 +0200, bartekltg <b...@g...com>
wrote:

Jeszcze jedna definicja

A stable (or independent) set in a graph is a set of pairwise
non-adjacent vertices

A.L.

do góry

W dniu 2014-07-02 00:30, bartekltg pisze:
> http://en.wikipedia.org/wiki/Maximum_disjoint_set
>
> Zastępujesz punkty kolami o srednicy równej minimalnemu dystansowi.
>
> Nadal NP-trudne.

A to coś zmienia? Ja zastępuję prostokąty różnych wielkości otaczające
elipsoidalne kształty punktami w ich środku. A odległość traktuję
binarnie - bliżej/nie bliżej

> Najprostszy zachłanny będzie liniowy względem rozmiaru grafu (V+E).

Tych punktów jest na tyle mało, że czas kwadratowy nie za bardzo
przeszkadza, ale w jaki sposób uzyskać czas liniowy?
Pierwszą częścią jest w ogóle uzyskanie grafu - tu biorę odległość każdy
z każdym, choć nie ma sensu brać odległości dwóch odległych punktów.
Potem jest właściwy algorytm. Liczba krawędzi wychodząca z każdego
wierzchołka jest mała w porównaniu z liczbą wierzchołków - mniejsza niż
pierwiastek, raczej kilka. Ale algorytm który stosuję jest kwadratowy,
ponieważ jedno szukanie maksymalnego wierzchołka jest liniowe -
przelatuje przez wszystkie wierzchołki, choć wiele ma po tyle samo krawędzi.

do góry

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

do góry

On 02.07.2014 07:19, Borneq wrote:
> W dniu 2014-07-02 00:30, bartekltg pisze:
>> http://en.wikipedia.org/wiki/Maximum_disjoint_set
>>
>> Zastępujesz punkty kolami o srednicy równej minimalnemu dystansowi.
>>
>> Nadal NP-trudne.
>
> A to coś zmienia? Ja zastępuję prostokąty różnych wielkości otaczające
> elipsoidalne kształty punktami w ich środku. A odległość traktuję
> binarnie - bliżej/nie bliżej

Przypadek ogólniejszy jest trudniejszy. NA dzień dobry w oryginalnym
masz heurystki oparte o gozkład geometryczny.

>
>> Najprostszy zachłanny będzie liniowy względem rozmiaru grafu (V+E).
>
> Tych punktów jest na tyle mało, że czas kwadratowy nie za bardzo
> przeszkadza, ale w jaki sposób uzyskać czas liniowy?

Bierzesz wierzchołek, wszystkich sąsiadów wyrzucasz. Bierzesz
pierwszy wolny wierzchołek, wyrzucasz wszystkich jego sąsiadów.
Powtarzasz do wyczerpania nieprzetworzonych wierzchołków.

Jest maksymalny, po dodanie jakiegokolwiek wyrzuconego nie jest
możliwe, stykał się z jakimś pozostawionym.

Czas to liczba krawędzi + liczba wierzchołków.

> Pierwszą częścią jest w ogóle uzyskanie grafu - tu biorę odległość każdy
> z każdym, choć nie ma sensu brać odległości dwóch odległych punktów.

Jeśli rozmiar obszaru jest przyzwoicie większy od rozmiaru
kulki/kwadratu, użyj jakiejś modyfikacji algorytmu zamiatania.
będzie znacznie szybciej.


> Potem jest właściwy algorytm. Liczba krawędzi wychodząca z każdego
> wierzchołka jest mała w porównaniu z liczbą wierzchołków - mniejsza niż
> pierwiastek, raczej kilka. Ale algorytm który stosuję jest kwadratowy,
> ponieważ jedno szukanie maksymalnego wierzchołka jest liniowe -
> przelatuje przez wszystkie wierzchołki, choć wiele ma po tyle samo
> krawędzi.

Skoro musisz wyrzucać je w tej kolejności, użyj jakiejś struktury,
gdzie masz kolejność i możesz 'pogarszać priorytet'. W najgorszym
przypadku ze std::set (drzewo binarne).

pzdr
bartekltg

do góry

W dniu 2014-07-02 11:52, bartekltg pisze:
>> Tych punktów jest na tyle mało, że czas kwadratowy nie za bardzo
>> przeszkadza, ale w jaki sposób uzyskać czas liniowy?
>
> Bierzesz wierzchołek, wszystkich sąsiadów wyrzucasz. Bierzesz
> pierwszy wolny wierzchołek, wyrzucasz wszystkich jego sąsiadów.
> Powtarzasz do wyczerpania nieprzetworzonych wierzchołków.

Jak biorę pierwszy wolny wierzchołek zamiast maksymalnego, to mi się nie
udaje. Np. 0-1-2, wyrzucam 0, zostaje 1-2, muszę wyrzucić 1

do góry

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.

do góry

On 02.07.2014 13:58, Borneq wrote:
> W dniu 2014-07-02 11:52, bartekltg pisze:
>>> Tych punktów jest na tyle mało, że czas kwadratowy nie za bardzo
>>> przeszkadza, ale w jaki sposób uzyskać czas liniowy?
>>
>> Bierzesz wierzchołek, wszystkich sąsiadów wyrzucasz. Bierzesz
>> pierwszy wolny wierzchołek, wyrzucasz wszystkich jego sąsiadów.
>> Powtarzasz do wyczerpania nieprzetworzonych wierzchołków.
>
> Jak biorę pierwszy wolny wierzchołek zamiast maksymalnego, to mi się nie
> udaje. Np. 0-1-2, wyrzucam 0, zostaje 1-2, muszę wyrzucić 1

I jest to zbiór niezależny maksymalny. Nikt nie obiecywał
największego;-)

Pewnie Twój średnio daje lepszy wynik, ale nie zawsze.
6
|
5
|
0-1-2-3-4
|
7
|
8

Tutaj Twój algorytm zwróci 4 elementy,
a da się 5.

pzdr
bartekltg

do góry