Ponto (grafeteorio)

Grafeo kun 16 verticoj kaj 6 pontoj (ruĝaj)

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

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

↑ 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 .

[1] 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 .

[robbins39-2] 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 .

[1]

[2]