Generowanie grafu spójnego

[PJW]

Cześć
W jaki sposób wygenerować losowy graf spójny (|V| = n, gdzie n jest
podane)? W literaturze i w sieci nie mogę znaleźć żadnego danego
algorytmu na ten problem.

Mam pewną koncepcję, otóż:

1. Tworzę rosnący ciąg: f(x) = x + 1, gdzie x należy do <0, n).

Np. dla n = 5.

1 2 3 4 5

2. Zamieniam elementy losowo tzn. swap(tab[i], tab[rand() % n]) w pętli
for i dostaje np. 3 2 1 5 4

3. Tworzę w ten sposób krawędzie i zachowuje spójność grafu:

3 -> 2 -> 1 -> 5 -> 4

Graf ten zapisuje np. w liście incydencji.

1 -> 2 -> 5
2 -> 3 -> 1
3 -> 2
4 -> 5
5 -> 1 -> 4

4. "Strzelam" losowo wartość z powyższego ciągu np. 5 i szukam węzła dla
tego węzła, by stworzyć nową krawędź. (tutaj pomijam węzły 1 i 4, więc
szukam wśród węzłów 2 i 3)

Algorytm dosyć skomplikowany i nieprzyjemny w implementacji. Macie
jakieś inne koncepcje lub ewentualnie ulepszenia do powyższego algorytmu?

Pozdrawiam,
PJW

[piotrek]

Post by PJW
Cześć
W jaki sposób wygenerować losowy graf spójny (|V| = n, gdzie n jest
podane)? W literaturze i w sieci nie mogę znaleźć żadnego danego
algorytmu na ten problem.
1. Tworzę rosnący ciąg: f(x) = x + 1, gdzie x należy do <0, n).
Np. dla n = 5.
1 2 3 4 5
2. Zamieniam elementy losowo tzn. swap(tab[i], tab[rand() % n]) w pętli
for i dostaje np. 3 2 1 5 4
3 -> 2 -> 1 -> 5 -> 4
Graf ten zapisuje np. w liście incydencji.
1 -> 2 -> 5
2 -> 3 -> 1
3 -> 2
4 -> 5
5 -> 1 -> 4
4. "Strzelam" losowo wartość z powyższego ciągu np. 5 i szukam węzła dla
tego węzła, by stworzyć nową krawędź. (tutaj pomijam węzły 1 i 4, więc
szukam wśród węzłów 2 i 3)
Algorytm dosyć skomplikowany i nieprzyjemny w implementacji. Macie
jakieś inne koncepcje lub ewentualnie ulepszenia do powyższego algorytmu?
Pozdrawiam,
PJW

Zakładam, że masz na myśli graf nieskierowany.

jeśli |V| = n - 1 to tworzymy graf spójny i acykliczny (czyli drzewo),
żeby mieć |V| = n, to dodajemy dodatkowo jedną losową krawędź

Moja propozycja wygląda tak:
// Budujemy drzewo (wierzchołki od 1 do n)
V = {1} // korzeń
E = {}
for i = 2 to n {
// wszystkie wierzchołki
// w V są ponumerowane od 1 do i-1
// wylosowany wierzchołek rozszerzamy o jedną krawędź
u = random(1, i-1)
v = i
wstaw do E krawędź (u, v)
wstaw do V wierzchołek o numerze v
}

// i dodatkowa krawędź
// (może zajść, że u = v, albo że krawędź (u, v) już jest w E)
u = random(1, n)
v = random(1, n)
wstaw do E krawędź (u, v)

[Marcin 'Qrczak' Kowalczyk]

Post by piotrek
jeśli |V| = n - 1 to tworzymy graf spójny i acykliczny (czyli drzewo),
żeby mieć |V| = n, to dodajemy dodatkowo jedną losową krawędź

Przez V tradycyjnie oznacza się zbiór wierzchołków (vertices),
więc uwaga o dodatkowej krawędzi jest bez sensu.

[piotrek]

Post by Marcin 'Qrczak' Kowalczyk

Post by piotrek
jeśli |V| = n - 1 to tworzymy graf spójny i acykliczny (czyli drzewo),
żeby mieć |V| = n, to dodajemy dodatkowo jedną losową krawędź

Przez V tradycyjnie oznacza się zbiór wierzchołków (vertices),
więc uwaga o dodatkowej krawędzi jest bez sensu.
--
__("< Marcin Kowalczyk
^^ http://qrnik.knm.org.pl/~qrczak/

Oj, ale gafę strzeliłem... Racja :) Przeczytałem |V| = n, a
potraktowałem jakby |E| = n
Właściwie wytłumaczyłem, jak wygenerować drzewo. Mój błąd.

Ale jak już mamy drzewko, graf będzie na pewno spójny.
Wtedy ileś razy możemy losować u i v, wstawiając nową krawędź.

Po poprawce:
// Budujemy drzewo (wierzchołki od 1 do n)
V = {1} // korzeń
E = {}
for i = 2 to n {
// wszystkie wierzchołki
// w V są ponumerowane od 1 do i-1
// wylosowany wierzchołek rozszerzamy o jedną krawędź
u = random(1, i-1)
v = i
wstaw do E krawędź (u, v)
wstaw do V wierzchołek o numerze v
}

for i = 1 to ile chcemy krawędzi dodatkowo {
u = random(1, n)
v = random(1, n)
wstaw do E krawędź (u, v)
}

[PJW]

Post by piotrek
Zakładam, że masz na myśli graf nieskierowany.
jeśli |V| = n - 1 to tworzymy graf spójny i acykliczny (czyli drzewo),
żeby mieć |V| = n, to dodajemy dodatkowo jedną losową krawędź

Zapomniałem dodać, że graf może posiadać cykle, gdyż ten graf będzie mi
służyć do zbadania, czy graf posiada cykl Euler'a, czy też nie.

PJW