Object structure


Zastosowanie metody minimalnego drzewa rozpinającego (najkrótszego dendrytu) w ocenie efektywności i spójności sieci osadniczej województwa mazowieckiego = Application of the minimum spanning tree method in assessing the effectiveness and cohesion of the settlement network of Mazowieckie voivodeship


Przegląd Geograficzny T. 91 z. 2 (2019)


Śleszyński, Przemysław : Autor ORCID ; Sudra, Paweł : Autor ORCID



Place of publishing:


Date issued/created:



24 cm

Type of object:


Subject and Keywords:

minimum spanning tree ; the shortest dendrite ; cohesion and effectiveness of settlement network ; dispersion of buildings ; spatial chaos ; Mazowieckie voivodeship


Contemporary settlement systems observed in Poland bear numerous traces of historical transformations of rural settlements which took place in the 19th century, at the time of foreign partitioning of Polish territory, in different ways in particular regions. The result of processes occurring from the second half of the 20th century is the extensive development of urban areas, and – after 1990 – chaotic, spontaneous processes of transformation in suburban zones. Research methods using graph theory have been applied for years in investigating settlement networks on various scales. One of the more useful graphs is the minimum spanning tree (MST), which connects all vertices in such a way that the sum of the distances between them is the shortest. This article presents the application of the minimum spanning tree (or shortest dendrite) method with a view to its suitability for determining the degree of dispersion and spatial cohesion of urbanised structures being assessed. Two indicators have been proposed thanks o alignment of the shortest dendrite length to other variables. The settlement network effectiveness indicator is the ratio of MST length to the population in an area. The settlement network cohesion indicator is in turn the ratio of the MST length to population density. Mazowieckie voivodeship has been chosen as the research area, while address points obtained from the central official database collecting data from municipal records have been chosen as the source dataset. Over 1 million address points were considered, in line with their status as at the end of 2016. Minimum spanning trees were plotted for each of the 314 gminas (local-authority areas) aking up the voivodeship, using ArcGIS software. Subsequently, the proposed indicators were calculated by reference to the MSTs. The results were then mapped. The proposed indicators may be helpful in studies on the origin of settlements, allowing areas with varying degrees of uniformity or isolation of building locations to be indicated. They can be made use of in comparative studies, especially concerning rural settlements, in which single-family housing predominates, and hamlets and uildings standing in isolation are present. The effectiveness indicator can be used in the assessment of infrastructural coverage, i.a. in the ontext of the costs of spatial chaos and demographic capacity.


1. Alonso-Villar O., 2011, Measuring concentration: Lorenz curves and their decompositions, The Annals of Regional Science, 47, 2, s. 451-475. https://doi.org/10.1007/s00168-010-0369-5
2. Arbia G., Espa G., Giuliani D., 2015, Analysis of spatial concentration and dispersion [w:] C. Karlsson, M. Andersson, T. Norman (red.), Handbook of Research Methods and Applications in Economic Geography, Edward Elgar Publishing, s. 135-157. https://doi.org/10.4337/9780857932679.00012
3. Assunção R.M., Neves M.C., Câmara G., Da Costa Freitas C., 2006, Efficient regionalization techniques for socio-economic geographical units using minimum spanning trees, International Journal of Geographical Information Science, 20, 7, s. 797-811. https://doi.org/10.1080/13658810600665111
4. Batyk I.M., 2010, Dziedzictwo kulturowe Warmii, Infrastruktura i Ekologia Terenów Wiejskich, 2, s. 34-43.
5. Boots B., Getis A., 1988, Point pattern analysis, Sage University Paper Series on Quantitative Applications in the Social Sciences, series no. 07-001, Sage Publications.
6. Borůvka O., 1926, O jistém problému minimálním, Práce Moravské přírodovědecké společnosti, 3, 3, s. 37-58.
7. Broitman D., Czamanski D., 2012, Cities in competition, characteristic time, and leapfrogging developers, Environment and Planning B: Planning and Design, 39, 6, s. 1105-1118. https://doi.org/10.1068/b37073
8. Bunn A.G., Urban D.L., Keitt T.H., 2000, Landscape connectivity: A conservation application of graph theory, Journal of Environmental Management, 59, 4, s. 265-278. https://doi.org/10.1006/jema.2000.0373
9. Chazelle B., 2000, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the Association for Computing Machinery, 47, 6, s. 1028-1047. https://doi.org/10.1145/355541.355562
10. Chilczuk M., 1975, Osadnictwo wiejskie. Metody badań koncentracji zabudowy i kształtów wsi, PWN, Warszawa.
11. Choquet G., 1938, Étude de certains réseaux de routes, Comptes Rendus de l'Académie des Sciences, 206, s. 310-313.
12. Clark P.J., Evans F.C., 1954, Distance to nearest neighbor as a measure of spatial relationships in population, Ecology, 35, 4, s. 445-453. https://doi.org/10.2307/1931034
13. Dijkstra E. W., 1959, A note on two problems in connexion with graphs, Numerische Mathematik, 1, 1, s. 269-271. https://doi.org/10.1007/BF01386390
14. Domański R., 1970, Syntetyczna charakterystyka obszaru na przykładzie Okręgu Przemysłowego Konin-Łęczyca-Inowrocław, Komitet i Zakład Badań Rejonów Uprzemysławianych, PWN, Warszawa.
15. Domański B., Guzik R., Gwosdz K., Micek G., 2010, Rozwój i struktura regionu w perspektywie długiego trwania - przypadek Małopolski, [w:] A. Kukliński, K. Pawłowski, J. Woźniak (red.), Polonia quo vadis? Urząd Marszałkowski Województwa Małopolskiego, Kraków, s. 181-211.
16. Duczkowska-Kądziel A., Duda J., Wasilewski M., 2013, Application of the minimum spanning tree (MST) approach to searching for an optimum location of biomass storage, Chemik, 67, 10, s. 935-944.
17. Florek K., Łukaszewicz J. Perkal J., Steinhaus H., Zubrzycki S., 1951, Taksonomia wrocławska, Przegląd Antropologiczny, 17, s. 193-211.
18. Gibas P., Heffner K., 2018, Społeczne i ekonomiczne koszy bezładu przestrzeni - osadnictwo obszarów wiejskich, [w:] A. Kowalewski, T. Markowski, P. Śleszyński (red.), Koszty chaosu przestrzennego, Studia KPZK PAN, 182, 2, Warszawa, s. 163-195.
19. Gieysztor A., Samsonowicz H. (red.), 1994, Dzieje Mazowsza do 1526 roku, PWN, Warszawa.
20. Gini C., 1912, Variabilità e mutabilità, Studi economico-giuridici pubblicati per cura della Facoltà di Giurisprudenza della Regia Università di Cagliari, 3, 2, s. 211-382.
21. Golachowski S., Kostrubiec B., Zagożdżon A., 1974, Metody badań geograficzno-osadniczych, PWN, Warszawa.
22. Graham R.L., Hell P., 1985, On the history of the minimum spanning tree problem, Annals of the History of Computing, 7, 1, s. 43-57. https://doi.org/10.1109/MAHC.1985.10011
23. Jarník V., 1930, O jistém problému minimálním (z dopisu panu O. Borůvkovi), Práce moravské přírodovědecké společnosti, 6, 4, s. 57-63.
24. Jaroš V., 2017, Social and transport exclusion, Geographia Polonica, 90, 3, s. 247-263. https://doi.org/10.7163/GPol.0099
25. Jażdżewska I., 2008, Przemiany miejskiej sieci osadniczej w Polsce w świetle metod matematycznych, Wydawnictwo Uniwersytetu Łódzkiego, Łódź.
26. Jażdżewska I., 2018, The use of centrographic measures in analysing the dispersion of historic factories, villas and palaces in Łódź (Poland), Folia Geographica, 60, 1, s. 50-61.
27. Kansky K., 1963, Structure of transportation networks: relationships between network geometry and regional characteristics, Research Paper, 84, Department of Geography, University of Michigan, Michigan.
28. Karger D., Klein P., Tarjan R., 1995, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM, 42, 2, s. 321-328. https://doi.org/10.1145/201019.201022
28. Kostrubiec B., 1972, Analiza zjawisk koncentracji w sieci osadniczej - problemy metodyczne, Prace Geograficzne, 93, Instytut Geografii PAN, Warszawa.
29. Koter M., 1980, Kształtowanie się strefy podmiejskiej w świetle badań historyczno-geograficznych, [w:] Pojęcia i metody badań strefy podmiejskiej. Materiały XIII Łódzkiej Konferencji Naukowej 19-20 I 1980, Wydawnictwo UŁ, Łódź, s. 1-17.
30. Kowalewski A., Markowski T., Śleszyński P. (red.), 2018, Studia nad chaosem przestrzennym, Studia KPZK PAN, 182, 1-3, Warszawa.
31. Kruskal J.B., 1956, On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, 7, s. 48-50. https://doi.org/10.2307/2033241
32. Liepelt S., Mayland-Quellhorst E., Lahme M., Ziegenhagen B., 2010, Contrasting geographical patterns of ancient and modern genetic lineages in Mediterranean Abies species, Plant Systematics and Evolution, 284, 3-4, s. 141-151. https://doi.org/10.1007/s00606-009-0247-8
33. Liszewski S., Wolaniuk A., 1998, Centra miast polskich w okresie transformacji (przykład Łodzi), [w:] T. Markowski, T. Marszał (red.), Gospodarka przestrzenna miast polskich w okresie transformacji, Biuletyn KPZK PAN, 182, s. 129-151.
34. Mackaness W.A., Beard K.M., 1993, Use of Graph Theory to Support Map Generalization, Cartography and Geographic Information Systems, 20, 4, s. 210-221. https://doi.org/10.1559/152304093782637479
35. Miedwiedkow J.V., 1966, Regularnaja komponenta w sietach rassielenija izobrazennych nakartie,Izwiestia AN SSSR, Seria Gieograficzeskaja, 4, s. 110–122.
36. Miszewska B., 1976, Morfologia sieci osadniczej jako układu linii, Acta Universitatis Wratislaviensis, 302, Studia Geograficzne, 22, Państwowe Wydawnictwo Naukowe, Warszawa-Wrocław.
37. Nystuen J.D., Dacey M.F., 1968, A graph theory interpretation of nodal regions, Geographia Polonica, 15, s. 135-152.
38. Owsiński J.W., Śleszyński P., 2016, Modelling of the social, economic and spatial transformations in the Province of Masovia, Geographia Polonica, 89, 2, s. 251-257.
39. Parysek J.J., 1985, Zróżnicowanie struktury społeczno-ekonomicznej głównych miast Jugosławii, Czasopismo Geograficzne, z. 3-4, s. 327-341.
40. Paulov J., Bezák A., 2017, Constraints as factors reducing the entropy of distributions: an entropy-maximizing spatial interaction model as an example, Przegląd Geograficzny, 89, 4, s. 517-533. https://doi.org/10.7163/PrzG.2017.4.1
41. Plit J., 1996, Antropogeniczne i naturalne przeobrażenia krajobrazów roślinnych Mazowsza (od schyłku XVIII w. do 1990 r.), Prace Geograficzne, 166, IGiPZ PAN, Warszawa.
42. Pomianowski W., 2018, Wpływ struktury sieci transportowej na dostępność przestrzenną. Dynamiczne ujęci grafowe, IGiPZ PAN, Warszawa (rozprawa doktorska).
43. Potrykowski M., Taylor Z., 1982, Geografia transportu. Zarys problemów, modeli i metod badawczych, PWN, Warszawa.
44. Prim R.C., 1957, Shortest connection networks and some generalizations, Bell System Technical Journal, 36,6, s. 1389-1401. https://doi.org/10.1002/j.1538-7305.1957.tb01515.x
45. Ratajczak W., 1977, Metody grafowe w geografii ekonomicznej [w:] Z. Chojnicki (red.), Metody ilościowe i modele w geografii, PWN, Warszawa, s. 143-157.
46. Ruegg K.C., Smith T.B., 2002, Not as the crow flies: a historical explanation for circuitous migration in Swainson's thrush (Catharus ustulatus), Proceedings of the Royal Society, Biological Sciences, 269, s. 1375-1381. https://doi.org/10.1098/rspb.2002.2032
47. Runge J., 1992, Wybrane zagadnienia analizy przestrzennej w badaniach geograficznych, Skrypty Uniwersytetu Śląskiego, 469, Uniwersytet Śląski, Katowice.
48. Runge A., Runge J., 2008, Słownik pojęć z geografii społeczno-ekonomicznej, Videograf Edukacja.
49. Shannon C.E., 1948, A mathematical theory of communication, Bell System Technical Journal, 27, s. 379-423, 623-656. https://doi.org/10.1002/j.1538-7305.1948.tb00917.x
50. Sollin G., 1965, Le tracé de canalisation, [w:] C. Berge, A. Ghouilla-Houri (red.), Programming, Games, and Transportation Networks, John Wiley & Sons, London.
51. Solon J., Pomianowski W., 2014, Program "GraphScape" - nowe narzędzie do analizy struktury przestrzennej i stopnia łączności w obrębie krajobrazu, Problemy Ekologii Krajobrazu, 38, s. 15-32.
52. Stępniak M., 2014, Przekształcenia przestrzennego rozmieszczenia zasobów mieszkaniowych w Warszawie w latach 1945-2008, Prace Geograficzne, 245, IGiPZ PAN, Warszawa.
53. Sudra P., 2016, Zastosowanie wskaźników koncentracji przestrzennej w badaniu procesów urban sprawl, Przegląd Geograficzny, 88, 2, s. 247-272. https://doi.org/10.7163/PrzG.2016.2.6
54. Sudra P., 2018, Ewolucja kryteriów delimitacji wielkomiejskich układów osadniczych w Polsce, Przegląd Geograficzny, 90, 2, s. 181-208. https://doi.org/10.7163/PrzG.2018.2.1
55. Sviatlovsky E., Eells W.C., 1937, The centrographical method and regional analysis, Geographical Review, 27, 2, s. 240-254. https://doi.org/10.2307/210093
56. Szmytkie R., 2014, Metody analizy morfologii i fizjonomii jednostek osadniczych, Rozprawy Naukowe Instytutu Geografii i Rozwoju Regionalnego, 35, Uniwersytet Wrocławski, Wrocław.
57. Szulc H., 1995, Morfogeneza osiedli wiejskich w Polsce, Prace Geograficzne, 163, IGiPZ PAN, Warszawa.
58. Śleszyński P. (red.), 2013, Wskaźniki zagospodarowania i ładu przestrzennego w gminach, Biuletyn KPZK PAN, 252, Warszawa.
59. Śleszyński P., 2014, Transport- and settlement-related time efficiency of road journeys taken in Poland, Geographia Polonica, 87, 1, s. 157-160. https://doi.org/10.7163/GPol.2014.10
60. Śleszyński P., Bański J., Degórski M., Komornicki T., 2017, Delimitation of problem areas in Poland, Geographia Polonica, 90, 2, s. 131-138. https://doi.org/10.7163/GPol.0088
61. Śleszyński P., Komornicki T., 2016, Klasyfikacja funkcjonalna gmin Polski na potrzeby monitoringu planowania przestrzennego, Przegląd Geograficzny, 88, 4, s. 469-488. https://doi.org/10.7163/PrzG.2016.4.3
62. Śleszyński P., Solon J., 2017, A map of the landscape diversity of Poland, Geographia Polonica, 90, 3, s. 369-377. https://doi.org/10.7163/GPol.0100
63. Śleszyński P., Stępniak M., Mazurek D., 2018, Oszacowanie skutków presji inwestycyjnej i nadpodaży gruntów budowlanych w strefie podmiejskiej Warszawy na przykładzie gmin pasma zachodniego, Przegląd Geograficzny, 90, 2, s. 209-240. https://doi.org/10.7163/PrzG.2018.2.2
64. Śleszyński P., Wiśniewski R., Szejgiec-Kolenda B., 2018b, Demographic processes in Poland in the years 1946-2016 and their consequences for local development: Current state and research perspectives, Geographia Polonica, 91, 3, s. 317-334. https://doi.org/10.7163/GPol.0123
65. Thomas R.W., 1981, Information Statistics in Geography, Geo Abstracts, University of East Anglia, Norwich, United Kingdom.
66. Uhorczak F., 1932, Z metodyki badań nad osadnictwem, Czasopismo Geograficzne, 10, 1-3, s. 11-28.
67. Verzosa L.C.O., Gonzalez R.M., 2010, Remote sensing, geographic information systems and shannon's entropy: Measuring urban sprawl in a mountainous environment [w:] W. Wagner, B. Székely (red.), ISPRS TC VII Symposium - 100 Years ISPRS, IAPRS, 38, 7A, Wiedeń, s. 269-274.
68. Węcławowicz G., 1996, Contemporary Poland. Space and society, UCL Press, London.
69. Wędzik A., 2014, The optimization of cable layout design in wind farm internal networks, Acta Energetica, 3, 20, s. 144-149. https://doi.org/10.12736/issn.2300-3022.2014313
70. Wiśniewski R., Szejgiec-Kolenda B., Śleszyński P., 2016, Population changes and population ageing in Poland between 1960 and 2011, Geographia Polonica, 89, 2, s. 259-265. https://doi.org/10.7163/GPol.0056
71. Wong D.W.S., 1999, Several fundamentals in implementing spatial statistics in GIS: Using centrographic measures as examples, Geographic Information Sciences, 5, 2, s. 163-174. https://doi.org/10.1080/10824009909480525
72. Wolny A., Źróbek R., 2017, The interdependence between suburban enclaves and the road network in the development process: a case study in Poland, Geographia Polonica, 90, 2, s. 41-57. https://doi.org/10.7163/GPol.0086
73. Yeh A.G.O., Li X., 2001, Measurement and monitoring of urban sprawl in a rapidly growing region using entropy, Photogrammetry and Remote Sensing, 67, 1, s. 83-90.
74. Zaborowski T., 2018, Land acquisition and land value capture instruments as determinants of public urban infrastructure provision: A comparison of the Polish legal framework with its German counterpart, Geographia Polonica, 91, 3, s. 353-369. https://doi.org/10.7163/GPol.0125
75. Zaborski B., 1926, O kształtach wsi w Polsce i ich rozmieszczeniu, Prace Komisji Etnograficznej PAU, 1, Kraków.
76. Zagożdżon A., 1970, Metody grafowe w badaniach osadnictwa, ze szczególnym uwzględnieniem morfologii siedlisk, Przegląd Geograficzny, 42, 2, s. 335-334.
77. Zagożdżon A., 1971, Morfologia osiedli województwa opolskiego [w:] S. Golachowski (red.), Struktury i procesy osadnicze, 2, Opole-Wrocław, Instytut Śląski, s. 321-372.
78. Zagożdżon A., 1977, Wykorzystanie metod i technik grafowych w analizie struktur przestrzennych [w:] Z. Chojnicki (red.), Metody ilościowe i modele w geografii, PWN, Warszawa, s. 158-169.
79. Zuziak Z.K., 1998, Strategie rewitalizacji przestrzeni śródmiejskiej, Monografie, 236, Politechnika Krakowska.


Przegląd Geograficzny





Start page:


End page:


Resource type:


Detailed Resource Type:



File size 1,7 MB ; application/octet-stream

Resource Identifier:

2300-8466 (on-line) ; 10.7163/PrzG.2019.2.4


CBGiOS. IGiPZ PAN, sygn.: Cz.181, Cz.3136, Cz.4187 ; click here to follow the link



Language of abstract:



Creative Commons Attribution BY 4.0 license

Terms of use:

Copyright-protected material. [CC BY 4.0] May be used within the scope specified in Creative Commons Attribution BY 4.0 license, full text available at: ; -

Digitizing institution:

Institute of Geography and Spatial Organization of the Polish Academy of Sciences

Original in:

Central Library of Geography and Environmental Protection. Institute of Geography and Spatial Organization PAS

Projects co-financed by:

Operational Program Digital Poland, 2014-2020, Measure 2.3: Digital accessibility and usefulness of public sector information; funds from the European Regional Development Fund and national co-financing from the state budget.





Citation style: