Neusmjereni graf
Neusmjereni graf, vrsta grafa iz teorije grafova.
Graf je u gruboj definiciji skup objekata: vrhova, točaka ili čvorova koje povezuju bridovi odnosno crte (linije). Brid spaja dva čvora i to je odnos koji definira graf. Ako vrhove povezuje brid, grafove se prikazuje crtanjem točaka za svaki vrh i povlačenjem luka između dvaju vrhova.[1]
Skup bridova u grafu obično se označava s E(G). Bridovi mogu biti usmjereni ili ne. Ako su grafu svi bridovi usmjereni, tad je graf usmjereni graf (digraf), u suprotnom je neusmjereni graf.[1]
Za pravi graf uzima se da je neusmjeren i kod njega crta od točka u do točke v istovjetna je crti od v do točke u. Kod usmjerenog grafa ta dva smjera nisu istovjetna i smatra ih se različitim bridovima (lukovima). Brid kod usmjerenih grafova može biti usmjeren od jednog vrha prema drugome.[1]
Neusmjerenost grafa jedan je od uvjeta da graf bude jednostavan.[1]
Ako je graf povezan i neusmjeren, razapinjuće stablo u tom grafu je podgraf koji je stablo i razapinje taj graf.[1]
Neusmjerenim grafom može se riješiti problem kineskog poštara i problem trgovačkog putnika.[1]