Page 362 - Srednje skole - radovi

TEORIJA GRAFOVA
GRAPH THEORY

Autor: MILOŠ KALIĈANIN, IV-7 Elektrotehniĉka škola ,,Nikola Tesla“,Beograd
Mentor: VIOLETA KOMNENOVIĆ, diplomirani matematiĉar Elektrotehniĉka škola
,,Nikola Tesla“,Beograd

REZIME

Cilj rada je upoznavanje sa grafovima uz pomoć definicija iteorema, kao i postavka problema i dolazak do

rešenja na razliĉite naĉine. U radu će biti navedene opšte osobine i neke vrste grafova poput Ojlerovog i
Hamiltonovog, što predstavlja teorijsko upoznavanje sa grafovima. Praktiĉna primena tog znanja ogledaće se

u analizi i rešavanju problema na razliĉite naĉine. Primena teorije grafova je široka i najviše je zastupljena u

programiranju, ali moţe se primeniti i u svakodnevnom ţivotu, na primer, tokom voţnje automobila, šetnje,
itd.

Kljuĉne reĉi: teorija grafova, Ojlerov graf, Hamiltonov ciklus,teţinski grafovi, problem trgovaĉkog putnika,

problem kineskog poštara.

SUMMARY

The aim of the work is introduction to graphs by using definitions and theorems as well as setting the

problem and coming to conclusion in different ways. In this piece of work some general characteristics and

some sorts of graphs such as Eulerian or Hamiltonian will be specified, which is the theoretical side of
getting a knowlegde of graphs. The practical use of this knowlegde will be shown in analysis and solving the

problems in different ways. The use of graphs theory is very wide and mostly can be found in programming,
but it can also be applied in everyday’s life, for example, while driving a car or walking.

Key words: graph theory, Eulerian graph, Hamiltonian cycle, weighted graphs, the problem of a commercial

traveller, the problem of a Chinese postman.