Döngü (grafik teorisi) - Loop (graph theory)

Köşe 1'de döngü içeren bir grafik

İçinde grafik teorisi, bir döngü (ayrıca a öz döngü veya a toka) bir kenar bağlayan tepe kendisine. Bir basit grafik döngü içermez.

Bağlama bağlı olarak, bir grafik veya a çoklu grafik döngülerin varlığına izin vermek veya vermemek için tanımlanabilir (genellikle izin verme veya engelleme ile uyum içinde) çoklu kenarlar aynı köşeler arasında):

  • Grafiklerin şu şekilde tanımlandığı yer: izin vermek döngüler ve çoklu kenarlar, döngüleri veya birden çok kenarı olmayan bir grafik, diğer grafiklerden genellikle buna bir basit grafik.
  • Grafiklerin şu şekilde tanımlandığı yer: izin vermemek döngüler ve çoklu kenarlar, döngüleri veya birden çok kenarı olan bir grafik genellikle bu kısıtlamaları karşılayan grafiklerden bir çoklu grafik veya sahte yazı.

Tek tepe noktası olan bir grafikte, tüm kenarlar döngü olmalıdır. Böyle bir grafiğe buket.

Derece

Bir ... için yönsüz grafik, derece bir köşe noktası, sayısına eşittir bitişik köşeler.

Özel bir durum, dereceye iki ekleyen döngüdür. Bu, döngü kenarının her bağlantısının kendi bitişik köşesi olarak sayılmasına izin verilerek anlaşılabilir. Başka bir deyişle, bir döngü içeren bir köşe, kendisini, her ikisi de kenarın uçları böylece dereceye bir değil iki ekler.

Bir Yönlendirilmiş grafik, döngü bir tane ekler derece olarak ve biri çıkış derecesi.

Ayrıca bakınız

Grafik teorisinde

Topolojide

Referanslar

  • Balakrishnan, V. K .; Grafik teorisiMcGraw-Hill; 1. baskı (1 Şubat 1997). ISBN  0-07-005489-4.
  • Bollobás, Béla; Modern Grafik Teorisi, Springer; 1. baskı (12 Ağustos 2002). ISBN  0-387-98488-7.
  • Diestel, Reinhard; Grafik teorisi, Springer; 2. baskı (18 Şubat 2000). ISBN  0-387-98976-5.
  • Gross, Jonathon L ve Yellen, Jay; Çizge Teorisi ve Uygulamaları, CRC Press (30 Aralık 1998). ISBN  0-8493-3982-0.
  • Gross, Jonathon L ve Yellen, Jay; (eds); Çizge Teorisi El Kitabı. CRC (29 Aralık 2003). ISBN  1-58488-090-2.
  • Zwillinger, Daniel; CRC Standart Matematik Tabloları ve Formülleri, Chapman & Hall / CRC; 31'inci baskı (27 Kasım 2002). ISBN  1-58488-291-3.

Dış bağlantılar