Ponto (grafeteorio)
eĝo ne apartenanta en ajna ciklo
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
redaktiEkvivalenta 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- ↑ 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.