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

Posty: 14
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 02:13 
Użytkownik
Avatar użytkownika

Posty: 1229
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 
 Czy może istnieć graf spełniający takie warunki?  magnes  1
 graf dwudzielny  kamil.jack  1
 Graf - dla podanego ciagu liczb wierzchołków  zxcvkolos  1
 graf trójkątny  matinf  0
 dla jakich n istnieje graf n-wierzochołkowy o st.3wierzchołk  bastek91  5
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl