najmniejsza liczba wierzchołków

pytanie zadane 18 listopada 2018 w Algorytmy przez Kuba321 Użytkownik (730 p.)

Witam,

mam problem grafowy: Dany jest graf skierowany. W ilu najmniej wierzchołkach trzeba rozpocząć przeszukiwanie grafu, by odwiedzić cały graf? Wydaje mi się, że "śmierdzi" to silnie spójnymi składowymi - dla grafu nieskierowanego szukana liczba byłaby po prostu liczbą spójnych składowych, ale w grafie nieskierowanym... tu zaczynają się dla mnie schodki. Proszę o pomoc - jakieś sugestie, albo sposób.

Pozdrawiam

1 odpowiedź

odpowiedź 18 listopada 2018 przez vector Dyskutant (9,200 p.)
wybrane 21 listopada 2018 przez Kuba321

Najlepsza

W grafie nieskierowanym jest to liczba spójnych składowych.

W grafie skierowanym jest to liczba wierzchołków z stopniem wejściowym równym 0 w grafie G(V, E). Gdzie V := {silnie spójne składowe oryginalnego grafu} (u, v) należy do E wtw istnieją dwa wierzchołki x, y takie że x należy do u, y należy do v oraz istnieje krawędź z x do y.

komentarz 18 listopada 2018 przez Kuba321 Użytkownik (730 p.)

Więc mam kolejne pytanie - stopień wejściowy ma coś wspólnego z silnie spójnymi składowymi? (tak się dopytuję, bo nadal mi się wydaje, że mój problem ma coś wspólnego z nimi)

komentarz 18 listopada 2018 przez vector Dyskutant (9,200 p.)

Tak masz rację, zapomniałem napisać w jakim grafie trzeba szukać tych wierzchołków o stopniu 0.

komentarz 18 listopada 2018 przez Kuba321 Użytkownik (730 p.)

Czyli w silnie spójnych składowych mam szukać tych wierzchołków? A jeżeli żadnego nie znajdę odp to 1?

komentarz 18 listopada 2018 przez vector Dyskutant (9,200 p.)

Czyli w silnie spójnych składowych mam szukać tych wierzchołków?

W grafie silnie spójnych składowych oryginalnego grafu.

A jeżeli żadnego nie znajdę odp to 1?

Tak, ponieważ jeżeli w grafie silnie spójnych składowych nie istnieje wierzchołek o stopniu 0 to oryginalny graf posiada 0 wierzchołków, więc odp to 1. Dzieje się tak, ponieważ graf silnie spójnych składowych jest skierowanym grafem acyklicznym.

komentarz 18 listopada 2018 przez Kuba321 Użytkownik (730 p.)

Jest na to jakiś szybszy sposób, czy można tak po prostu przeszukiwać i obliczać?

komentarz 18 listopada 2018 przez vector Dyskutant (9,200 p.)

Nie wiem czy rozumiem pytanie.

Jeżeli chodzi Ci o złożoność obliczeniową to nie ponieważ algorytm jest liniowy od wejścia.

Jeżeli pytasz czy istnieje jakiś algorytm online tego problemu to nie wiem.