Forbundet graf

En forbundet graf  er en graf , der indeholder præcis én tilsluttet komponent . Det betyder, at der er mindst én vej mellem ethvert par af hjørner i denne graf .

Applikationseksempler

En direkte anvendelse af grafteori er netværksteori - og dens anvendelse er elektronisk netværksteori. For eksempel danner alle computere, der er tilsluttet internettet, en forbundet graf, og selvom et separat par computere muligvis ikke er direkte forbundet (i formuleringen for grafer, ikke forbundet med en kant), kan information overføres fra hver computer til evt. andet (der er en sti fra et hvilket som helst toppunkt på grafen til et hvilket som helst andet).

Tilslutning til rettede grafer

I rettede grafer skelnes der mellem flere begreber om tilslutning.

En rettet graf siges at være stærkt forbundet , hvis den har en (rettet) vej fra et hvilket som helst toppunkt til et hvilket som helst andet, eller tilsvarende, grafen indeholder præcis én stærkt forbundet komponent .

En rettet graf kaldes svagt forbundet , hvis det er en forbundet urettet graf opnået fra den ved at erstatte rettede kanter med urettede.

Nogle tilslutningskriterier

Her er nogle kriterium (ækvivalente) definitioner af en forbundet graf:
En graf kaldes simpelthen forbundet (forbundet), hvis:

  1. Den har en tilsluttet komponent
  2. Der er en sti fra et hvilket som helst toppunkt til et hvilket som helst andet toppunkt
  3. Der er en sti fra et givet toppunkt til et hvilket som helst andet toppunkt
  4. Indeholder en forbundet undergraf, der inkluderer alle hjørner af den originale graf
  5. Indeholder som en undergraf et træ, der inkluderer alle hjørnerne af den originale graf (et sådant træ kaldes et spændingstræ )
  6. Når dets hjørner er vilkårligt opdelt i 2 grupper, er der altid mindst 1 kant, der forbinder et par knudepunkter fra forskellige grupper

Se også