[ 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: 4282
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 
 Droga eulera
Witam, otóż mam mały problem z zadaniem domowym i chcialbym jezeli ktos ma chec i moglby pomoc to prosze o to Rysunek niżej to plan budynku. czy mozna obejsc caly ...
 Siwy033  4
 Najkrótsza droga w grafie
Witam. Pani profesor z matematyki zadała mi na zaliczenia napisanie programu, który ma znajdować najkrótszą drogę z wierzchołka A do B. Graf będę wprowadzał do programu za pomocą macierzy sąsiedztwa. I tutaj pojawia się problem. Jaki jest algorytm na...
 wojciech007  1
 definicja orientacji
Witam czy mogłby mi ktos wyjasnic tą definicje? Niech G bedzie grafem i niech C bedzie kolorowaniem G k+1 barwami. Dla kazdej permutac...
 nati10222  0
 Łą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
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [Reklama] [Kontakt]
Copyright (C) ParaRent.com