szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Kobieta Offline
PostNapisane: 31 maja 2012, o 17:39 
Użytkownik

Posty: 141
Lokalizacja: Miasto
Witam, nie rozumiem pojęcia droga. Są różne definicje.

Rozumiem, że droga to marszruta bez powtarzających się wierzchołków (z wyjątkiem krawędzi pierwszego i ostatniego) i krawędzi.

Natomiast jest taka własność, która mówi, że "kolejne potęgi macierzy sąsiedztwa digrafu, odpowiadają macierzy zawierającej liczbę dróg pomiędzy wierzchołkami".

Przykład grafu skierowanego:
Obrazek

jest 19 dróg długości 5:
np. są 2 drogi zaczynające się od wierzchołka 1 do wierzchołka 1: dedcb, dcbde

jak widać, krawędzie się powtarzają, tak samo jest z wierzchołkami.

To jak w końcu jest? Mogą się powtarzać czy nie?
Góra
Mężczyzna Offline
PostNapisane: 1 cze 2012, o 20:55 
Użytkownik

Posty: 4527
Lokalizacja: Józefów
W przytoczonym przez Ciebie twierdzeniu chodzi o dowolne marszruty danej długości, czyli wierzchołki mogą się powtarzać. Jeśli przez drogę rozumiemy marszrutę, w której nie powtarzają się wierzchołki, to takie sformułowanie twierdzenia jest błędne.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Łączenie punktów + najkrótsza droga
Własnie mi coś z Zordonem uświadomiiście Wszyscy po trochu mieliśmy racji Np....
 Dasio11  48
 Droga prosta a spójność w grafie
G jest grafem spójnym, \delta (G)=k \ \wedge \ k \ge 1. Wówczas G zawiera drogę prostą P długości k-1[/tex:14j...
 silvaran  0
 definicja rekurencyjna ciągu ze wzorów
prosze o zrobienie i wytłumaczenie zadania bo całkowicie go nie rozumiem Definiujemy rekurencyjnie ciąg za pomocą wzorów a_{0}=a_{1}=1 oraz a_{n}=a_{n-1}+2a_{n-2} dla n \ge 2[/...
 lampid  1
 Ścieżka krytyczna i najkrótsza droga
Mam nadzieję,że odpowiedni dział wybrałem. Mam 2 zadani: Wyznaczyć dla poszczególnego zadania : -najwcześniejszą chwilę rozpoczęcia zadania -najpóźniejszą chwilę rozpoczęcia zadania -najwcześniejszą chwilę zakończenia zadania -najpóźniejszą chwil...
 finapliks  0
 Wykazać, że w grafie Petersena istnieje droga Hamiltona
jw...
 stonek89  2
 Obwód i droga Eulera
A) Proszę o sprawdzenie rozwiązania. http://img831.imageshack.us/img831/8540/eulerm.jpg Obwód Eulera: 1, 3, 4, 7, 6, 3, 5, 6, 4, 2, 1 Droga Eulera: brak[/tex:3b...
 add00  3
 najkrotsza droga
mam rozwiązać zadanie które wyznacza najkrótszą drogę z punktu A do B przez C lub D. i nie wiem czy dobrze myśle. Musi to byś suma dróg a->c->b i a->d->c, czyli wyszlo by mi ostatecznie cos takiego: drogi(a->c->b) + drogi(a->d-...
 cfk  0
 Droga prosta w grafie
Nie wiem jak się zabrać za to zadanie: G jest grafem spójny, \delta(G)=k, k \ge 1. Wówczas G zawiera drogę prostą P długości [...
 rubik1990  0
 Definicja permutacji
Permutacją n-elementową z powtórzeniami zbioru X={x_1,...,x_k} w której elemnty x_1,...,x_kpowtarzają się n_1,...,n_k razy, przy czym n=n_1+...+n_k[/...
 myszka9  4
 definicja rekurencyjna ciągu
Podaj definicję rekurencyjną ciągu: (2, 2^2,2^{(2^2)}, 2^{(2^{(2^2)})}) tzn. ciągu (2, 4, 16, 65536, ...)...
 Demon  1
 Droga Hamiltona
Witam, mam problem z zadaniem: Udowodnij, że każdy skończony, zorientowany graf, w którym dowolne dwa wierzchołki są połączone dokładnie jedną krawędzią w jednym z dwóch możliwych kierunków posiada drogę Hamiltona. Pozdrawiam...
 THCFalcon  3
 Teoria grafów. Obwód i droga Eulera
Witam, proszę o sprawdzenie zadań z teorii grafów i o podanie prawidłowych odpowiedzi tam, gdzie mam błędy albo chociaż o wskazówki jak je zrobić. Z góry dziękuję za pomoc ...
 marcin00412  0
 Rekurencyjna definicja operacji odejmowania
Witam, jest to mój pierwszy post wiec, przepraszam z góry za jakiekolwiek błędy. Przedstaw rekurencyjna definicje odejmowania jedynki w liczbach naturalnych, ktora okreslana jest wzorem minus\left( x\right) = max\left\{ x-1, ...
 Tenshin  7
 Grafy eulerowskie, półeulerowski i droga w grafie.
Największą wątpliwość mam co do K_n w sumie wydaje mi się, że nie zawsze jest to graf Eulerowski.[/quote:18z685ob...
 jezarek  6
 definicja rekurencyjna ciągu - zadanie 3
Z liczb -1,0,1budujemy ciągi długości n w taki sposób aby -1 nie sąsiadowało z 0. Niech l_{n} będzie lic...
 olcia446  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com