Witam
Własnie zaczelismy nowy dział z dyskretnej
i znowu jestem zielony jest to moje pierwsze zadanie z grafów byc moze jest banalne ale nawet nie wiem jak do niego podejsc.
czy mozecie mi pomoc je rozwiazac?
3.Udowodnij, że jeżeli w grafie niezorientowanym istnieją dwa różne cykle zawierające tą samą krawędź, to istnieje także cykl nie zawierający owej krawędzi
z góry dzieki za wszelka pomoc
Nikomu nie polecam studiów internetowych
Udowodnij ze w grafie
-
Qń
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Udowodnij ze w grafie
Jeśli wierzchołki tej krawędzi to \(\displaystyle{ x,y}\), to wiemy z założenia, że istnieją dwa różne cykle:
\(\displaystyle{ x,v_1,v_2,\ldots , v_k, y,x}\)
i
\(\displaystyle{ x,u_1,u_2,\ldots , u_l, y,x}\)
gdzie \(\displaystyle{ v_i,u_i}\) są wierzchołkami grafu.
Nietrudno zauważyć, że
\(\displaystyle{ x,v_1,v_2,\ldots , v_k, y,u_l, u_{l-1},\ldots , u_1,x}\)
jest cyklem niezawierającym krawędzi \(\displaystyle{ xy}\).
Wystarczy sobie to narysować.
Q.
\(\displaystyle{ x,v_1,v_2,\ldots , v_k, y,x}\)
i
\(\displaystyle{ x,u_1,u_2,\ldots , u_l, y,x}\)
gdzie \(\displaystyle{ v_i,u_i}\) są wierzchołkami grafu.
Nietrudno zauważyć, że
\(\displaystyle{ x,v_1,v_2,\ldots , v_k, y,u_l, u_{l-1},\ldots , u_1,x}\)
jest cyklem niezawierającym krawędzi \(\displaystyle{ xy}\).
Wystarczy sobie to narysować.
Q.
-
TrzyRazyCztery
- Użytkownik
- Posty: 101
- Rejestracja: 24 maja 2014, o 17:53
- Płeć: Mężczyzna
- Lokalizacja: Wro
- Podziękował: 27 razy
- Pomógł: 1 raz
Udowodnij ze w grafie
Chciałem odkopać temat żeby nie zakładać nowego, czy ktoś potrafi pomóc w rozwiązaniu tego problemu dla rozcięć?