Grafuri-fisa de lucru 3
Fişa de lucru 3
1. Se consideră graful neorientat cu 7 noduri, numerotate de la 1 la 7, și muchiile [1,3], [2,3], [3,4], [3,5], [5,4], [1,2], [2,5], [2,4], [6,7], [3,6]. Care dintre următoarele succesiuni de noduri reprezintă un lanț care trece o singură dată prin toate nodurile grafului?
a. (1, 2, 3, 4, 5, 6, 7) b. (4, 5, 3, 6, 7) c. (7, 6, 3, 5, 4, 2, 1) d. (1, 3, 5, 4, 2, 3, 6)
2. Se consideră graful neorientat cu nodurile numerotate de la 1 la 6 și având muchiile [1,2], [2,3], [2,5], [2,6], [3,4], [4,5], [4,6], [5,6]. Câte lanțuri elementare, distincte și de lungime 3 există de la nodul 1 la nodul 4 în graful dat? Două lanțuri sunt distincte dacă diferă prin cel puțin o muchie.
2.Se consideră graful neorientat cu 6 noduri, definit cu ajutorul listelor de adiacența alăturate. Care dintre mulțimile următoare de noduri are toate elementele extremități ale unor lanțuri elementare de lungime 2 cu cealaltă extremitate în nodul 5?
1: 4,5,6
2: 5
3: 4
4: 1,3
5: 1,2,6
6: 1,5
3. Pentru următorul graf cu 5 noduri realizați:
a) câte circuite elementare de lungime 3 există în graf
b) câte circuite elementare există în graf
c) câte circuite de lungime maxima exista în graf
d) dați exemplu de un circuit de lungime maximă
e) dați exemplu de un drum elementar de lungime maximă dintre nodul 1 și nodul 4.
2. Fie un graf neorientat cu 6 noduri memorat prin următoarea listă de adiacență. Reprezentați grafic graful neorientat. Afișați toate lanțurile elementare de lungime 4 care pleacă din nodul 2.
1: 2 5 6
2:1 3 4
3:2 4 6
4:2 3 5
5:1 4 6
6: 1 3 5