Romana | English


2014 |2013 | 2012 |2011 | 2008 |2007 | 2006 | 2005 | 2004

Arbori partiali de cost minim
Premiul al II-lea Cupa Siveco 2005
Teoria grafurilor - o tema cu numeroase aplicatii practice - este de cele mai multe ori un subiect dificil pentru elevi.
Problema determinarii unui arbore partial de cost minim este una dintre temele cu multiple aplicatii economice, motiv pentru care am intordus aceasta problema, plecand de la doua exemple practice (proiectarea unei retele de calculatoare, respectiv problema reabilitarii drumurilor).
Am prezentat apoi problema in limbaj de grafuri, definind notiunile teoretice necesare si am prezentat doi algoritmi fundamentali de determinare a unui arbore partial de cost minim: Algoritmul lui Kruskal si algoritmul lui Prim.

Drumuri minime in graf
Mentiune Cupa Siveco 2005
O alta tema din teoria grafurilor cu numeroase aplicatii practice este problema determinarii drumurilor minime într-un graf.
Am prezentat aceasta tema plecand de la aplicatii practice familiare elevului, urmand apoi sa transpunem problema in limbaj de grafuri si sa prezentam 3 algoritmi de rezolvare a acestei probleme: algoritmul lui Dijkstra, algoritmul Roy-Floyd si algoritmul Belman-Ford.
Fiecare moment de lectie este insotit de elemente de evaluare.

© Emanuela Cerchez 2004