Liczba dróg w grafie.

Albatross201 · Post autor: **Albatross201** » 19 sie 2010, o 14:47

Witam mam do policzenia liczbe dróg w grafie tylko nie mam pojęcia jak wygląda graf \(\displaystyle{ P_{2} \cdot P_{2}}\). Prosiłbym narysowanie o chociażby w paincie byle jak tylko żebym miał zarys tego. Próbowalem policzyc z takiego grafu jaki uważałem za prawidłowy ale okazalo się że jednak nie wiem jak on wygląda.

Kartezjusz · Post autor: **Kartezjusz** » 19 sie 2010, o 14:52

Co oznacza zapis \(\displaystyle{ P_{2} \cdot P_{2}}\)?

Albatross201 · Post autor: **Albatross201** » 19 sie 2010, o 15:38

\(\displaystyle{ P_{n}}\) jest grafem dwudzielnym takim że \(\displaystyle{ V(P_{n})=\{x_{1},...,x_{n}\} \;i\; E(P_{n})=\{\{x_{i},x_{i+1}\};i=1,...,n-1\}\;,n \ge 1}\). Wówczas \(\displaystyle{ V(P_{n})=V_{1} \bigcup V_{2}}\), gdzie \(\displaystyle{ V_{1}}\) jest zbiorem wierzchołków o indeksach nieparzystych a \(\displaystyle{ V_{2}}\) zbiorem wierzchołków o indeksach parzystych. Oczywiście V to zbiór wierzchołków a E to zbiór krawędzi. Więc jak to będzie wyglądać?

Fingon · Post autor: **Fingon** » 19 sie 2010, o 16:08

Zapytam z ciekawości, skąd wziąłeś to zadanie?

Albatross201 · Post autor: **Albatross201** » 19 sie 2010, o 16:26

Ze skryptu "Matematyka Dyskretna" Andrzeja i Iwony Włoch. To co pomoże ktoś?

Kartezjusz · Post autor: **Kartezjusz** » 20 sie 2010, o 13:57

Ale to mnożenie? Niestety,teorię grafów mam przed sobą:-(

Albatross201 · Post autor: **Albatross201** » 22 sie 2010, o 22:14

Niech ktoś chociaż narysuje sam graf \(\displaystyle{ p_{2}}\) i \(\displaystyle{ P_{6}}\) według tego co napisałem wyżej. Bardzo mi na tym zależy.

miodzio1988 · Post autor: **miodzio1988** » 22 sie 2010, o 22:23

Albatross201, no to definicję masz....jaki problem jest żeby z niej skorzystać?

Albatross201 · Post autor: **Albatross201** » 22 sie 2010, o 23:07

Chce się po prostu upewnić. Bo jeżeli będziemy chcieli narysować \(\displaystyle{ P_{2}}\) to będziemy mieć x1 i x2 czego krawędź ma wglądać tak że łączy x1 z x2 bo \(\displaystyle{ E(P_{n})=\{\{x_{i},X_{i+2}\};i=1,...,n-1\}}\) ale jeśli popatrzymy na koniec warunku czyli n-1 to wychodzi na to że krawędź ma zrobić pętle z x1 do x1...więc jak to ma dokładnie wyglądać?
P6 ma tak wyglądać?

Uploaded with

miodzio1988 · Post autor: **miodzio1988** » 22 sie 2010, o 23:10

Jak zrobisz podział na dwa zbiory wierzchołków to problem mamy z głowy
Zatem? Pomysł jakiś?
-- 22 sierpnia 2010, 22:24 --

że krawędź ma zrobić pętle z x1 do x1..

No raczej nie...

Albatross201 · Post autor: **Albatross201** » 23 sie 2010, o 00:11

Z tego co mi wiadomo to \(\displaystyle{ V_{1}}\) ma być zbiorem wierzchołków o indeksach nieparzystych czyli wsadzimy tam \(\displaystyle{ x_{1}}\) a do \(\displaystyle{ V_{2}}\) wsadzimy \(\displaystyle{ x_{2}}\)...ale nadal nie jestem pewien jak ten graf ma wyglądać. Może mi ktoś odpowiedzieć?

miodzio1988 · Post autor: **miodzio1988** » 23 sie 2010, o 10:55

No to źle znasz definicje grafu dwudzielnego.

Albatross201 · Post autor: **Albatross201** » 23 sie 2010, o 11:32

miodzio1988 jestem wdzieczny za to że udzielasz sie w moim temacie i próbujesz mnie zmusić do myślenia i szukania ale widocznie nie jestem na tyle bystry żeby to pojąć a tutaj nie potrzebuje takich uwag tylko pomocy. Jeśli nie potrafisz pomóc to dziękuje Ci za samą chęć udziału w temacie ale jak potrafisz to pomóż bez zbednych komentarzy.

miodzio1988 · Post autor: **miodzio1988** » 23 sie 2010, o 11:36

Uwaga jest taka, żebyś zrozumiał definicję. Bo bez tego nie zrobisz żadnego zadania. Więc zamiast płakać tutaj na forum jaki to Miodek jest zły, weź się za zrozumienie definicji albo zadaj jakieś konkretne pytanie dotyczące tej definicji. Bo tracisz mój czas w tym momencie takim gadaniem