ALFA BK UNIVERZITET
FAKULTET ZA MATEMATIKU I RAČUNARSKE NAUKE
MASTER STUDIJE
SEMINARSKI RAD
Naslov: Grafovski algoritmi u programskom jeziku Pajton
TEORIJA ALGORITMA, JEZIKA I AUTOMATA
Mentor:
Student:
Beograd, 2019.godine
2
SADRŽAJ
UVOD
....................................................................................................................................... 3
1. OSNOVNI POJMOVI U TEORIJI GRAFOVA
.............................................................. 5
1.1. VRSTE I PODVRSTE GRAFOVA
............................................................................ 6
1.2. KRETANJE KROZ GRAF
......................................................................................... 8
1.3. USMERENI GRAF
...................................................................................................... 9
1.4. ТЕŽINSKI GRAF
...................................................................................................... 10
2. PROGRAMSKI JEZIK PAJTON
................................................................................... 12
2.1. OPŠTE KARAKTERISTIKE PROGRAMSKOG JEZIKA PAJTON
................. 12
2.1. PREDNOSTI I MANE PROGRAMSKOG JEZIKA PAJTON
............................ 12
3. PROJEKTOVANJE ALGORITAMA
............................................................................ 15
ZAKLJUČAK
........................................................................................................................ 19
LITERATURA
...................................................................................................................... 20
4
U prvom poglavlju ovog rada opisani su osnovni pojmovi u teoriji grafova. U drugom poglavlju
date su osnovne karakteristijke Pajton programskog jezika, dok su u trećem poglavlju
obradjena četiri zadatka iz oblasti projektovanja algoritama u programskom jeziku Pajton.
5
1. OSNOVNI POJMOVI U TEORIJI GRAFOVA
Graf je apstraktni matematički objekat, odnosno struktura koja opisuje odnose između nekih
objekata. Neformalno govoreći, grafove čine tačke (
čvorovi
), koje predstavljaju neke objekte
– vrhove, i linije između njih (
grane
), koje označavaju odnose između tih objekata.
Proučavanjem grafova bavi se teorija grafova (Petrović, 1998).
Graf je zadat ako su poznata dva skupa, skup čvorova V i skup grana E.
Definicija:
Graf
G
=
(
V
,
E
)
je uređeni par koji se sastoji od skupa čvorova V i skupa grana.
E
⊆ "
#
$
%
Primer
Čvorovi mogu biti gradovi, a grane putevi između njih.
Čvorovi mogu biti računari, a načini komunikacija između njih grane.
Slika 1.) Primer grafa
