BazEkon - Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie

BazEkon home page

Meny główne

Autor
Tarapata Zbigniew
Tytuł
O problemie zliczania dróg w grafach
On the Problem of Paths Counting in Graphs
Źródło
Badania Operacyjne i Decyzje, 2003, nr 2, s. 61-75, bibliogr. 13 poz.
Operations Research and Decisions
Słowa kluczowe
Teoria grafów, Grafy, Kombinatoryka, Metody numeryczne, Badania operacyjne
Graph theory, Graphs, Combinatorial analysis, Numerical methods, Operations research
Uwagi
streszcz., summ.
Abstrakt
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.

In the paper, the problem of paths counting in graphs is considered. Estimations of the number of paths and simple paths in simple graphs and Berge's graphs are given. It is proved that for full graphs the number of simple paths between any pair of nodes is equal to the number of some variations without repetitions. Recurrent formulas for paths counting and their computational complexities are given. Some results of estimation of the number of simple paths for selected graphs are presented. Finally, some conclusions and applications of presented estimations are indicated.
Dostępne w
Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka Szkoły Głównej Handlowej
Biblioteka Główna Uniwersytetu Ekonomicznego w Katowicach
Biblioteka Główna Uniwersytetu Ekonomicznego w Poznaniu
Biblioteka Główna Uniwersytetu Ekonomicznego we Wrocławiu
Bibliografia
Pokaż
  1. BRYANT V., Aspects of Combinatorics, University Press, Cambridge 1993.
  2. DEO N., Teoria grafów i jej zastosowania w technice i informatyce, PWN, Warszawa 1980.
  3. KORZAN B., Elementy teorii grafów i sieci. Metody i zastosowania, WNT, Warszawa 1978.
  4. KUBALE M. (red.), Optymalizacja dyskretna. Modele i metody kolorowania grafów, WNT, Warszawa 2002.
  5. KULIKOWSKI J.L., Zarys teorii grafów, PWN, Warszawa 1986.
  6. PALKA Z., RUCIŃSKi A., Wykłady z kombinatoryki, cz. I, Przeliczanie, WNT, Warszawa 1998.
  7. PAPADIMITRIOU CH.H., Złożoność obliczeniowa, WNT, Warszawa 2002.
  8. Poradnik inżyniera. Matematyka, cz. I, WNT, Warszawa 1986.
  9. TARAPATA Z., Some aspects of multi-convoy redeployment modelling and simulation, Proceedings of the 21st AFCEA Europe Symposium & Exposition, 18-20 October, Prague 2000 (CD publication).
  10. TARAPATA Z., Military route planning in battlefield simulation: effectiveness problems and potential solutions. Proceedings of The Regional Conference on Military Communication and Information Systems, 04-06 October, Zegrze (Poland) 2002, vol. I, 191-200.
  11. TARAPATA Z., Zliczanie dróg w grafach regularnych, Biuletyn Wojskowej Akademii Technicznej, Warszawa 2003 (w przygotowaniu).
  12. WILSON R.J., Wprowadzenie do teorii grafów, PWN, Warszawa 1998.
  13. WOŹNIAK M., Wprowadzenie do problemów komunikacji w grafach, Wydawnictwo AGH, Kraków 1999.
Cytowane przez
Pokaż
ISSN
1230-1868
Język
pol
Udostępnij na Facebooku Udostępnij na Twitterze Udostępnij na Google+ Udostępnij na Pinterest Udostępnij na LinkedIn Wyślij znajomemu