Najpierw opiszę poprzednie zadanie, z którym sobie dobrze radzi algorytm
o nazwie "Znajdowanie spójnych składowych w grafie"
http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol018.ph
p

Mamy graf o wierzchołkach 0..7
poszczególne wierzchołki są ze sobą połączone (połączenia dwukierunkowe)
0 z 1
1 z 2
3 z 4
5 z 6
6 z 7
7 z 5
Powyższy algorytm dzieli graf na składowe
A: 0,1,2
B: 3,4
C: 5,6,7

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.

Jeżeli mamy spójne składowe i wybieramy z każdej składowej po
wierzchołku, to możemy tak zrobić dla B i C. Natomiast dla A należy
usunąć wierzchołek 1 i zostawić 0 i 2.
Inny przykład: wierzchołki połączone w kolejkę:
0-1-2-3-4-5-6-7-8
Po operacji ma zostać: 0,2,4,6,8 - czyli co drugi
Jak to zalgorytmizować? Czy jest to znany problem? Jeśli tak, pod jaką
nazwą szukać?

do góry

On 2014-07-01, Borneq <b...@a...hidden.pl> wrote:
> Najpierw opiszę poprzednie zadanie, z którym sobie dobrze radzi algorytm
> o nazwie "Znajdowanie spójnych składowych w grafie"
> http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol018.ph
p
>
> Mamy graf o wierzchołkach 0..7
> poszczególne wierzchołki są ze sobą połączone (połączenia dwukierunkowe)
> 0 z 1
> 1 z 2
> 3 z 4
> 5 z 6
> 6 z 7
> 7 z 5
> Powyższy algorytm dzieli graf na składowe
> A: 0,1,2
> B: 3,4
> C: 5,6,7
>
> 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.
>
> Jeżeli mamy spójne składowe i wybieramy z każdej składowej po
> wierzchołku, to możemy tak zrobić dla B i C. Natomiast dla A należy
> usunąć wierzchołek 1 i zostawić 0 i 2.
> Inny przykład: wierzchołki połączone w kolejkę:
> 0-1-2-3-4-5-6-7-8
> Po operacji ma zostać: 0,2,4,6,8 - czyli co drugi
> Jak to zalgorytmizować? Czy jest to znany problem? Jeśli tak, pod jaką
> nazwą szukać?

Na pierwszy rzut okiem wygląda jak algorytm zachłanny na stopniu
wierzchołka. Możesz problem przeformułować: chcesz usunąć wszystkie
krawędzie minimalną liczbą ruchów, a każdą krawędź można usunąć
eliminując jeden z końców (procedura jak wyżej). Wtedy pewnie się będzie
dało dowieść, że algorytm niezachłanny da gorszy wynik.

--
Secunia non olet.
Stanislaw Klekot

do góry

W dniu 2014-07-01 16:02, Borneq pisze:
> 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.

Mam pewien pomysł:
Otóż gdy mamy 1 wierzchołek - nic nie musimy robić
gdy mamy połączone 0 z 1 - usuwamy 0 lub 1
gdy mamy 3 wierzchołki, mamy 3 przypadki różniące się tylko identyfikatorami
0-1-2: usuwamy 1
0-2-1: usuwamy 2
1-0-2: usuwamy 0
i przypadek trójkata 0-1-2 i 2 z 0: zostawiamy tylko jeden dowolny
wierzchołek. W pierwszej fazie usuwamy dowolny jeden wierzchołek
sprowadzając do dwóch wierzchołków.
Coś mi mówi, że w każdym kroku usuwamy ten wierzchołek, który ma
najwięcej krawędzi. Czy tak będzie?
Jak to optymalnie zrobić? Szukanie w każdym kroku maksymalnego da czas
kwadratowy, a porządek posortowania po ilości krawędzi zostanie zepsuty
po eliminacji wierzchołka

do góry

On 01.07.2014 16:02, Borneq wrote:
> Najpierw opiszę poprzednie zadanie, z którym sobie dobrze radzi algorytm
> o nazwie "Znajdowanie spójnych składowych w grafie"
> http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol018.ph
p
>
> Mamy graf o wierzchołkach 0..7
> poszczególne wierzchołki są ze sobą połączone (połączenia dwukierunkowe)
> 0 z 1
> 1 z 2
> 3 z 4
> 5 z 6
> 6 z 7
> 7 z 5
> Powyższy algorytm dzieli graf na składowe
> A: 0,1,2
> B: 3,4
> C: 5,6,7
>
> 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;-)

pzdr
bartekltg

do góry

W dniu 2014-07-01 18:46, bartekltg pisze:
> 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;-)

Dzięki za namiar!
Oryginalny problem to przerzedzanie punków:
Mam zbiór punktów, które są za gęste. Mam przerzedzić punkty - wybrać
zbiór puntów reprezentantów i zbiór punktów pozostałych, tak aby
reprezentanci nie byli bliżej od siebie niż jakaś odległość.

NP-trudny:
Widocznie rozwiązywałem w sposób za bardzo zachłanny. Ale może nie jest
taki ważny warunek, aby było jak najwięcej wierzchołków, wystarczy że
maksymalny w sensie inkluzji, że wystarczy jeden dodać i nie będzie
spełniony warunek.
Na razie obliczam w czasie kwadratowym, może nienajlepsze rozwiązanie to
tablica wektorów, w każdym z nich indeksy połączonych wierzchołków.
Myślę że jeśli chodzi o przerzedzanie punktów to wystarczy ten
zachłanny. Można by go teraz dostroić, bo w każdym kroku wybieram z
kilku o tej samej liczbie krawędzi do odrzucenia. Odrzucać mam taki,
który jak najmniej nadaje się na reprezentanta.

do góry

On Tue, 01 Jul 2014 18:46:08 +0200, bartekltg <b...@g...com>
wrote:

>On 01.07.2014 16:02, Borneq wrote:
>> Najpierw opiszę poprzednie zadanie, z którym sobie dobrze radzi algorytm
>> o nazwie "Znajdowanie spójnych składowych w grafie"
>> http://edu.i-lo.tarnow.pl/inf/utils/002_roz/ol018.ph
p
>>
>> Mamy graf o wierzchołkach 0..7
>> poszczególne wierzchołki są ze sobą połączone (połączenia dwukierunkowe)
>> 0 z 1
>> 1 z 2
>> 3 z 4
>> 5 z 6
>> 6 z 7
>> 7 z 5
>> Powyższy algorytm dzieli graf na składowe
>> A: 0,1,2
>> B: 3,4
>> C: 5,6,7
>>
>> 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_se
t#Finding_maximum_independent_sets
>
>Na zachętę, problem NP-trudny;-)
>
>pzdr
>bartekltg

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

A.L.

do góry

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.

Każda krawędź w grafie ma co najmniej jeden konic w dopełnieniu zbioru
niezależnego, więc zostanie usunięta. Dostajesz to, o co pyta Borneq.

pzdr
bartekltg

do góry

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

A.L.

do góry

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

do góry

On 01.07.2014 20:37, Borneq wrote:
> W dniu 2014-07-01 18:46, bartekltg pisze:
>> 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;-)
>
> Dzięki za namiar!
> Oryginalny problem to przerzedzanie punków:
> Mam zbiór punktów, które są za gęste. Mam przerzedzić punkty - wybrać
> zbiór puntów reprezentantów i zbiór punktów pozostałych, tak aby
> reprezentanci nie byli bliżej od siebie niż jakaś odległość.


Trzeba było od razu, a nie się czaić:)

http://en.wikipedia.org/wiki/Independent_set_%28grap
h_theory%29#Independent_sets_in_geometric_intersecti
on_graphs

http://en.wikipedia.org/wiki/Maximum_disjoint_set

Zastępujesz punkty kolami o srednicy równej minimalnemu dystansowi.

Nadal NP-trudne.

> NP-trudny:
> Widocznie rozwiązywałem w sposób za bardzo zachłanny. Ale może nie jest
> taki ważny warunek, aby było jak najwięcej wierzchołków, wystarczy że
> maksymalny w sensie inkluzji, że wystarczy jeden dodać i nie będzie
> spełniony warunek.

Taki nazywa się maksymalnym (Maximal independent set)

Skoro odpowiada Ci rozwiązanie przybliżone, użyj heurystyk,
najlepiej dla oryginalnego, prostszego problemu.

> Na razie obliczam w czasie kwadratowym, może nienajlepsze rozwiązanie to
> tablica wektorów, w każdym z nich indeksy połączonych wierzchołków.
> Myślę że jeśli chodzi o przerzedzanie punktów to wystarczy ten
> zachłanny. Można by go teraz dostroić, bo w każdym kroku wybieram z
> kilku o tej samej liczbie krawędzi do odrzucenia. Odrzucać mam taki,
> który jak najmniej nadaje się na reprezentanta.

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

pzdr
bartekltg

do góry