Îmbunătățește-ți Cunoștințele de Informatică, Dezvoltă-ți Abilitățile de Programare și Design Web!
Definiţie: Se numeşte ciclu hamiltonian un ciclu elementar care trece prin toate vârfurile grafului. Un graf care admite un ciclu hamiltonian se numeşte graf hamiltonian. Fie G = (X,U) un graf neorientat şi un lanţ elementar care trece prin toate nodurile grafului [x0,x1, …, xn]. Dacă d(x1) + d(xn)≥n atunci graful este hamiltonian. Fie G … Read more
Definiţie: Un graf se numeşte graf conex dacă pentru oricare două vârfuri x şi y diferite ale sale, există un lanţ care le leagă, adică x este extremitatea iniţială şi y este extremitatea finală.Un graf cu un singur nod este, prin definiţie, conex. Definiţie: Se numeşte componentă conexă a unui graf G = (X,U) un … Read more