[feed] pefprints@pef.uni-lj.si | [feed] Atom [feed] RSS 1.0 [feed] RSS 2.0 |
English
Logo            
  Logo Prijava | Registracija
 
 

Algoritem za iskanje krepkih komponent v usmerjenem grafu

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

[img]
Predogled
PDF
Download (581Kb)

    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