Hej,
Jakiego algorytmu uzyc do wyszukania najblizszego wspolnego
wierzcholka w grafie skierowanym (bez cykli, zaczynajac od danego
wierzcholka)? Z tego co wyszukalem problem zdaje sie jest podobny to
znajdowania dominatorow (BTW czy to jest poprawna polska nazwa?) tylko
ze nie mam do niego algorytmu. Na razie mysle zeby znalezc liste
wszystkich sciezek od wierzcholka startowego, z list wybrac
wierzcholki ktore sa kazdej sciezce i wybrac tego ktorego droga od
poczatku jest najmniejsza. Czy ma to sens? Wolalbym jednak uzyc
sprawdzonej metody, ktora prawdopodobnie bylaby lepsza od mojej dosc
"prymitywnej".

do góry

On Thu, 8 Apr 2010 09:47:57 -0700 (PDT), ternyk <t...@g...com>
wrote:

>Jakiego algorytmu uzyc do wyszukania najblizszego wspolnego

Wspolnego dla kogo?

> od wierzcholka startowego,

To jest wejscie algorytmu?

milego dnia, hej

do góry

Maciej Pilichowski wrote:
> Wspolnego dla kogo?
Wspolnego dla wszystkich drog wychodzacych z wierzcholka startowego. Na
wejsciu jest graf oraz wierzcholek startowy, na wyjsciu najblizszy
wspolny wierzcholek, lub jego brak.

do góry

W dniu 2010-04-09 08:56, ternyk pisze:
> Maciej Pilichowski wrote:
>> Wspolnego dla kogo?
> Wspolnego dla wszystkich drog wychodzacych z wierzcholka startowego. Na
> wejsciu jest graf oraz wierzcholek startowy, na wyjsciu najblizszy
> wspolny wierzcholek, lub jego brak.

Jeśli szukasz wierzchołka wspólnego dla wszystkich dróg wychodzących z
wierzchołka startowego to wystarczy, że sprawdzić stopień wyjściowy
wierzchołka s(tartowego):
1) |out(s)| == 0 brak
2) |out(s)| == 1 odpowiedzią jest jedyny element zbioru out(s)
3) |out(s)| > 1 brak, ponieważ istnieje zbiór ścieżek postaci (s, x e
out(s)), które nie mają żadnego wspólnego wierzchołka

Przypuszczam jednak, że miałeś na myśli jakiś inny problem tylko nie
sprecyzowałeś go należycie.

Pozdrawiam, W

do góry

i...@a...domain.com wrote:
> Jeśli szukasz wierzchołka wspólnego dla wszystkich dróg wychodzących z
> wierzchołka startowego to wystarczy, że sprawdzić stopień wyjściowy
> wierzchołka s(tartowego):
> 1) |out(s)| == 0 brak
> 2) |out(s)| == 1 odpowiedzią jest jedyny element zbioru out(s)
> 3) |out(s)| > 1 brak, ponieważ istnieje zbiór ścieżek postaci (s, x e
> out(s)), które nie mają żadnego wspólnego wierzchołka

Dzieki. Ale raczej na pewno nie wystarczy mi sprawdzenie stopnia
wierzchołka startowego.

> Przypuszczam jednak, że miałeś na myśli jakiś inny problem tylko nie
> sprecyzowałeś go należycie.

Wydawało mi się, że jasno wytłumaczyłem problem, no ale może już nie
ważne bo znalazłem o co mi chodziło: problem w teorii znany jest pod
hasłem "[finding] immediate postdominators" (w polskich materiałach na
temat grafów nie znalazłem polskiej nazwy o ile istnieje).

--
pozdrowienia,
ternyk

do góry