# Algoritem za iskanje krepkih komponent v usmerjenem grafu

Nikola Ivačič (2012) Algoritem za iskanje krepkih komponent v usmerjenem grafu. Diplomsko delo.

 Predogled
PDF

## Povzetek

This thesis gives a detailed description of an algorithm for finding strongly connected components in a directed graph. The reader requires no prior knowledge of graph theory or algorithm analisys. We start by introducing graph theory as a problem space and a framework for a given algorithm. We define some fundamental constructs such as: what is a digraph, what are strongly connected components, and what are their basic properties. A description of a theoretical model of computation comes next. It serves as a founda- tion for the study of algorithm complexity and its correctness in general. We learn what is an algorithm, what is its complexity and correctness. In order to analyse the algorithm for constructing strongly connected components of a given digraf we need to get familiar with basic datastructures and mathematical tools for algorithm construction. In the core of the thesis we present the algorithm of Tarjan, of Kusaraju-Sharir and the algorithm of Cheriyan-Mehlhorn/Gabow, together with the analisys of their complexity and proof of their correctenes. We deal with how the graph is presented in our model of computation and with mathematical theorems that are used as building blocks for the construction and analisys of the three algorithms.

Tip vnosa: Delo ali doktorska disertacija (Diplomsko delo)
Ključne besede: usmerjen graf, krepke komponente povezanosti, algoritem, Turingov stroj, časovna kompleksnost, iskanje v globino, Tarjanov algoritem, Kosarajujev algoritem, algoritem Cheriyan–Mehlhorn/Gabow-a
Število strani: 57
Jezik vsebine: Slovenščina
Mentor / Somentorji:
Mentor / SomentorjiIDFunkcija
izr. prof. dr. Aleksander MalničMentor
Povezava na COBISS: http://www.cobiss.si/scripts/cobiss?command=search&base=50126&select=(ID=9586249)
Ustanova: Univerza v Ljubljani
Fakulteta: Pedagoška fakulteta
ID vnosa: 1373
Datum vnosa: 02 Apr 2013 07:02
Zadnja sprememba: 02 Apr 2013 07:02
URI: http://pefprints.pef.uni-lj.si/id/eprint/1373

### Akcije (potrebna je prijava)

 Pregled vnosa


Your browser does not support iframes.

PeFprints vzdružuje EPrints 3, ki je bil razvit na School of Electronics and Computer Science na Univerzi Southampton. Več informacij... .