Dudirekta grafeo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo

En grafeteorio, dudirekta grafeo estas grafeo en kiu al ĉiu latero estas donita sendependa orientiĝo (aŭ direkto, aŭ sago) je ĉiu fino.

Tial, estas tri specoj de dudirektaj lateroj:

  • tiuj kie la sagoj montras eksteren, al la verticoj, je ambaŭ finoj;
  • tiuj kie ambaŭ sagoj montras enen, for de la verticoj;
  • tiuj en kiu unu sago montras for de ĝia vertico kaj al la kontraŭa fino, kaj la alia sago montras en la sama direkto kiel la unua, for de la kontraŭa fino kaj al ĝia propra vertico.

Lateroj de ĉi tiuj tri specoj povas nomiĝi, respektive, kiel eksteren-direktitaj, enen-direktitaj, kaj direktitaj. La direktitaj lateroj estas la samaj kiel ordinaraj direktaj lateroj en orientita grafeo; tial, orientita grafeo estas speciala speco de dudirekta grafeo.

Estas iam dezirinde havi ankaŭ laterojn kun nur unu fino (duono-lateroj); ĉi tiuj havas nur unu sagon. lateroj sen finoj (laksa latero) ne havas sagojn. Lateroj kiuj estas nek duono-lateroj nek laksaj lateroj estas ordinaraj lateroj.

Vidu ankaŭ[redakti | redakti fonton]