Grafy losowe

• Autorzy: Rybarczyk K.

Warianty tytułu

EN

Random graphs

• Języki publikacji: PL

Abstrakty

PL

Uznaje się, że graf losowy po raz pierwszy został wykorzystany w 1947 w pracy Erdősa. Został on wtedy użyty do wyznaczenia oszacowania dolnego liczby Ramseya. Analiza własności grafów losowych, jako obiektów będących samodzielnym przedmiotem badań, została zapoczątkowana o wiele później dwiema pracami Erdősa i Rényiego, które ukazały się na przełomie lat pięćdziesiątych i sześćdziesiątych. Prace te wyznaczyły kierunki badań, charakter stawianych pytań dotyczących grafów losowych, a także pozostawiły wiele interesujących problemów otwartych, które nadal są inspiracją dla matematyków. Artykuł ten ma na celu przedstawić w sposób przystępny zagadnienia poruszane w teorii grafów losowych i kierunki jej rozwoju. Zaczniemy od trzech klasycznych modeli grafów losowych. Następnie zaprezentujemy podstawowe problemy rozpatrywane w pracach Erdősa i Rényiego i opiszemy, jak wpłynęły one na kierunki badań dotyczących grafów losowych. Później przedstawimy niektóre metody dowodowe wykorzystywane w teorii. Opiszemy także jeden z wielu przykładów zastosowań grafów losowych w innych dziedzinach nauki. Zakończymy przykładem nowego kierunku badań z pogranicza dziedzin matematyki, który jest ściśle powiązany z teorią grafów losowych.

Słowa kluczowe

PL

graf losowy; graf Erdősa i Rényiego; graf prosty; graf k-regularny; graf pełny; graf spójny; podgraf; modelowanie sieci

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Wiadomości Matematyczne
• Rocznik: 2015
• Tom: T. 51, Nr 1
• Strony: 7--24
• Opis fizyczny: Bibliogr. 27 poz.

Twórcy

autor

Rybarczyk K.

• Wydział Matematyki i Informatyki, Uniwersytet im. Adama Mickiewicza w Poznaniu

Bibliografia

• [1] R. Albert, A-L. Barabási, Emergence of scaling in random networks, Science 286 (1999). 509-512.
• [2] N. Alon, J. Spencer, The Probabilistic Method, John Wiley & Sons 2000.
• [3] S. Antoniuk, T. Łuczak, J. Świątkowski, Random triangular groups at density 1/3, dostępne pod adresem arXiv:i3o8.5867.
• [4] M. Bloznelis, J. Jaworski, E. Godehardt, V. Kurauskas, K. Rybarczyk, Recent progress in complex network analysis: Models of random intersection graphs, [w:] Data Science, Learning by Latent Structures, and Knowledge Discovery (B. Lausen, S. Krolak-Schwerdt, M. Bóhmer, red.), Springer 2015, 69-78.
• [5] M. Bloznelis, J. Jaworski, E. Godehardt, V. Kurauskas, K. Rybarczyk, Recent progress m complex network analysis: Properties of random intersection graphs, [w:] Data Learning by Latent Structures, and Knowledge Discovery (B. Lausen, S. Krolak-Schwerdt, M. Böhmer, red.), Springer 2015, 79-88.
• [6] B. Bollobás, Random Graphs, Academic Press 1985.
• [7] B. Bollobás, S. Janson, O. Riordan, The phase transition in inhomogeneous random gmp i Random Structures & Algorithms 31 (2007), nr 1, 3-122.
• [8] P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292-294.
• [9] P. Erdős, A. Rényi, On random graphs I, Publicationes Mathematicae Debrecen 6 (1959), 290-297.
• [10] P. Erdős, A. Rényi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci. 5 (1960).
• [11] P. Erdős, J. Spencer, Probabilistic methods in combinatorics, Akademia Kiadó 1974.
• [12] A. Frieze, M. Karoński, Introduction to Random Graphs, Cambridge University Press, w przygotowaniu.
• [13] E. N. Gilbert, Random graphs, Annals of Mathematical Statistics 30 (1959), nr 4, 1141-1144.
• [14] E. Godehardt, J. Jaworski, Two models of random intersection graphs for classification, [w:] Studies in Classification, Data Analysis and Knowledge Organization (O. Opitz, M. Schwaiger, red.), t. 22, Springer 2003, 67-81.
• [15] R. van der Hofstad, Random Graphs and Complex Networks, preprint.
• [16] S. Janson, D. E. Knuth, T. Łuczak, B. Pittel, The birth of the giant component, Random Structures & Algorithms 4 (1993), nr 3, 233-358.
• [17] S. Janson, T. Łuczak, A. Ruciński, Random Graphs, Wiley 2001.
• [18] M. Karoński, A. Ruciński, The Mathematics of Paul Erdős I, Algorithms and Combinatorics, t. 13, Springer 1997, 311-336.
• [19] M. Karoński, E. R. Scheinerman, K. B. Singer-Cohen, On random intersection graphs: The subgraph problem, Combinatorics, Probability and Computing 8 (1999), 131-159.
• [20] R. M. Karp, The transitive closure of a random digraph, Random Structures & Algorithms 1 (1990), nr 1, 73-93.
• [21] M. Newman, A.-L. Barabási, D. J. Watts (red.), The Structure and Dynamics of Setworks, Princeton University Press 2006.
• [22] Z. Palka, A. Ruciński, O grafach losowych, Wiadomości Matematyczne 30 (1994), 175-197.
• [23] Z. Palka, A. Ruciński, Niekonstruktywne metody matematyki dyskretnej, Wydawnictwa Naukowo-Techniczne 1996.
• [24] J. Spencer, N. Wormald, Birth control for giants, Combinatorica 27 (2007), nr 5, 587-628.
• [25] N. C. Wormald, Differential equations for random processes and random graphs, Annals of Applied Probability 5 (1995), 1217-1235.
• [26] N. C. Wormald, The differential equation method for random graph processes and greedy algorithms, [w:] Lectures on Approximation and Randomized Algorithms (M. Karoński, H. J. Prömel, red.), PWN 1999.
• [27] A. Żuk, Property (T) Kazhdan constants for discrete groups, Geometric and Functional Analysis 13 (2003), nr 3, 643-670.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę.