Ponto (grafeteorio)

eĝo ne apartenanta en ajna ciklo
Estas neniuj versioj de ĉi tiu paĝo, do ĝi eble ne estis kvalite kontrolita.

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.

Grafeo kun 16 verticoj kaj 6 pontoj (ruĝaj)
Sendirekta koneksa grafeo sen ponto

Senponta grafeo

redakti

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