Ponto (grafeteorio)
En grafeteorio, ponto estas eĝo tia, ke forigi ĝin multigas koneksajn komponantojn.[1] Ekvivalente, eĝo estas ponto se kaj nur se ĝi ne apartenas al iu ajn ciklo. Grafeo estas senponta se ĝi enhavas neniun ponton.
Senponta grafeo
[redakti | redakti fonton]Ekvivalenta kondiĉo de Senponta grafeo inkluzivas ke ĉiu koneksa komponanto havas malfermitan orelo-malkomponadon,[2] ke ĉiu koneksa komponanto estas koneksa per 2 eĝoj, aŭ (laŭ teoremo de Robbins) ke ĉiu koneksa komponanto havas fortan orienton.
Referencoj
[redakti | redakti fonton]- ↑ Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, 184, New York: Springer-Verlag, p. 6, doi:10.1007/978-1-4612-0619-4, (ISBN 0-387-98488-7), https://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA6.
- ↑ Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem of traffic control", The American Mathematical Monthly 46: 281–283, doi:10.2307/2303897.
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Cover photo is available under {{::mainImage.info.license.name || 'Unknown'}} license.
Credit:
(see original file).
