Issue: 2003/Vol.13/No.2, Pages 61-75
ON THE PROBLEM OF PATHS COUNTING IN GRAPHS
Zbigniew Tarapata
Cite as: Z. Tarapata. On the problem of paths counting in graphs. Operations Research and Decisions 2003: 13(2), 61-75.
Abstract
W pracy przedstawiono oszacowania na liczbę dróg oraz dróg prostych w grafach zwykłych oraz Berge’a. Dla grafów pełnych wykazano, że liczba dróg prostych między dowolną parą wierzchołków jest równa liczbie pewnych wariacji bez powtórzeń. Podano rekurencyjne procedury wyliczania (dla grafów pełnych) lub szacowania (dla grafów niepełnych) liczby dróg prostych oraz oszacowano ich złożoności obliczeniowe. Przedstawiono wyniki oszacowań liczby dróg prostych dla wybranych grafów.
Keywords: graf, procedura rekurencyjna, droga
Received: Accepted: