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
Instytut Matematyczny, Uniwersytet Wrocławski
Mężczyzna Offline
PostNapisane: 1 cze 2012, o 20:55 
Użytkownik

Posty: 4764
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 
 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
 Rekurencyjna definicja ciągu
Dla każdego n \ge 1 niech t_n oznacza liczbę ciągów o długości n zbudowanych z liter a, b, ...
 gosiak5321  6
 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
 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
 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
 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
 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
 Rekurencyjne definicja ciagu
Dana jest rekurencyjna definicja ciągu. Znajdź wzór ogólny na n-ty wyraz ciągu a_0= 2, a_n= 2a_{n-1}+ 3 dla n>0. Odpowiedź poprzyj dowodem....
 Szalony_Ryszard  1
 definicja rekurencyjna ciągu - zadanie 2
mógłby mi ktoś wytłumaczyć i zrobić zadanie bo nie rozumiem tego zad. Podaj definicję rekurencyjną ciągu: a) (2, 2^{2}, (2^{2})^2, ((2^2)^2)^2[/tex:3san2p...
 lampid  1
 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
 Budowanie ciągu i definicja rekurencyjna
Z liczb {-1}, {0}, {1} budujemy ciągi długości n w taki sposób aby {-1} nie sąsiadowała {0}. Niech l_{n} będzie liczbą takich ciągów....
 Paylinka07  1
 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
 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
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) ParaRent.com