szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Graf skierowany
PostNapisane: 6 wrz 2017, o 14:36 
Użytkownik

Posty: 10
Lokalizacja: localhost
Niech będzie dany pewien graf skierowany G = \left\langle V, A \right\rangle, gdzie A \subseteq V^{2}
a) Jaką interpretację można przypisać złożeniu relacji A?
b) Co oznaczają elementy relacji A^{2}, ..., A^{n}?
c) Co oznacza A^{*}?
d) W jaki sposób można zbadać, czy graf posiada cykl?
Góra
Mężczyzna Offline
PostNapisane: 13 wrz 2017, o 01:13 
Użytkownik
Avatar użytkownika

Posty: 1202
Jeśli chodzi o (b), to elementem relacji A^k będzie para wierzchołków, które są k-incydentne, tj istnieje droga (czy tam ścierzka, nie wiem za dużo o terminologii) długości k, która łączy te dwa wierzchołki.

Wydaje mi się też, że domknięcie relacji reprezentowanej przez taki graf skierowany na fajną "grafową" interpretacje. To są po prostu wszystkie pary, wierzchołków, między którymi istnieje ścierzka skończonej długości.

A, i graf ma cykl, jeśli istnieje taki v\in V oraz takie k\in\omega, że (v,v)\in A^k.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Dany jest graf  laki_me  1
 Jaka macierz przyległości aby WKKW na spójny graf - zadanie 2  sweetdream  2
 Wykaż, że... graf spójny - wierzchołki - jednakowe stopnie  gabilu  1
 Graf 8 wierzchołków i 2 składowe spójne  zielony789  6
 Graf - cykle  midek  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl