Loop (grafteori) - Loop (graph theory)

En graf med en slinga på topp 1

I grafteorin är en slinga (även kallad en självslinga eller ett spänne ) en kant som ansluter ett toppunkt till sig själv. En enkel graf innehåller inga loopar.

Beroende på sammanhanget kan en graf eller ett multigraf definieras så att antingen tillåta eller tillåta närvaron av slingor (ofta tillsammans med att tillåta eller tillåta flera kanter mellan samma hörn):

  • Där grafer definieras så att slingor och flera kanter tillåts , skiljer sig ofta ett diagram utan loopar eller flera kanter från andra grafer genom att kalla det en enkel graf .
  • Där grafer definieras så att slingor och flera kanter inte tillåts , skiljer sig ofta ett diagram som har loopar eller flera kanter från graferna som uppfyller dessa begränsningar genom att kalla det en multigraf eller pseudograf .

I en graf med ett toppunkt måste alla kanter vara slingor. En sådan graf kallas en bukett .

Grad

För ett oriktat diagram är graden av en topp lika med antalet intilliggande hörn .

Ett speciellt fall är en slinga som lägger till två i graden. Detta kan förstås genom att låta varje anslutning av slingkanten räknas som sitt eget intilliggande toppunkt. Med andra ord "ett toppunkt med en slinga" ser "sig själv som ett intilliggande toppunkt från båda ändar av kanten och därmed lägger till två, inte en, till graden.

För en riktad graf lägger en slinga till en i in-grad och en till ut-grad .

Se även

I grafteori

I topologi

Referenser

  • Balakrishnan, VK; Grafteori , McGraw-Hill; 1 upplaga (1 februari 1997). ISBN   0-07-005489-4 .
  • Bollobás, Béla; Modern grafteori , Springer; 1: a upplagan (12 augusti 2002). ISBN   0-387-98488-7 .
  • Diestel, Reinhard; Grafteori , Springer; 2: a upplagan (18 februari 2000). ISBN   0-387-98976-5 .
  • Gross, Jonathon L och Yellen, Jay; Grafteori och dess tillämpningar , CRC Press (30 december 1998). ISBN   0-8493-3982-0 .
  • Gross, Jonathon L och Yellen, Jay; (red.) Handbok för grafteori . CRC (29 december 2003). ISBN   1-58488-090-2 .
  • Zwillinger, Daniel; CRC-matematiska standardtabeller och formler , Chapman & Hall / CRC; 31: a upplagan (27 november 2002). ISBN   1-58488-291-3 .

externa länkar