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?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 13 wrz 2017, o 02:13 
Użytkownik
Avatar użytkownika

Posty: 1227
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 
 Spójny graf prosty - wymiar  niunian  0
 czy istnieje graf o stopniach wierzchołków  anilahcim  2
 Jak wyglada graf  ablazowa  2
 Graf planarny bez trójkątów  lidka95  1
 koło a graf Eulera  manduka  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl