Calea (teoria graficelor)

O cale într-un grafic este o succesiune de vârfuri în care fiecare vârf este conectat la marginea următoare.

Definiții

Fie G un graf nedirecţionat . O cale în G este o succesiune finită sau infinită de muchii și vârfuri [1] , $S = (..., a_0,E_0, a_1, E_1, ..., E_{n-1}, a_n, ...)$

că fiecare două muchii adiacente și au un vârf comun . $E_{i-1}$ $E_{i}$ $a_{i}$

Astfel, se poate scrie $..., E_0=(a_0,a_1), E_1=(a_1,a_2), ... , E_n=(a_n,a_{n+1}), ...$

Rețineți că aceeași muchie poate apărea de mai multe ori într-o cale. Dacă nu există muchii care precedă , atunci se numește vârful inițial al lui S, iar dacă nu există muchii care urmează , atunci se numește vârful final al lui S. Orice vârf care aparține două muchii adiacente se numește intern . Deoarece muchiile și vârfurile pot fi repetate într-o cale, un vârf interior poate fi vârful de început sau de sfârșit. $E_{0}$ $a_{0}$ $E_{(n-1)}$ $un$

Dacă vârfurile de început și de sfârșit sunt aceleași, calea se numește ciclică . O cale se numește lanț , iar o cale ciclică se numește ciclu , dacă fiecare dintre marginile sale apare cel mult o dată (vârfurile pot fi repetate). O cale non- ciclică se numește cale simplă dacă nu se repetă niciun vârf în ea. Un ciclu cu un capăt se numește ciclu simplu dacă nu este un vârf intermediar în el și nu se repetă alte vârfuri. $a_{0}$ $a_{0}$

Din păcate, această terminologie nu este bine stabilită. Wilson [2] a scris:

Ceea ce am numit un traseu se mai numește și o cale, o secvență de margini.

Lanțul se numește cale, cale semi-simplu; a simple chain - un lanț, o cale, un arc, o cale simplă, un lanț elementar; un circuit închis - un circuit ciclic, un circuit; ciclu - un contur, un circuit de contur, un ciclu simplu, un ciclu elementar.

— [3] [4] [5]

Căile, lanțurile și ciclurile sunt concepte fundamentale în teoria grafurilor și sunt definite în partea introductivă a majorității cărților de teoria grafurilor. Vezi, de exemplu, Bondi și Marty [6] , Gibbons [7] sau Distel [8] .

Diferite tipuri de căi

O cale pentru care nicio margine a graficului nu conectează două vârfuri ale căii se numește cale indusă .

O cale simplă care conține toate vârfurile unui grafic fără repetări este cunoscută sub numele de cale hamiltoniană .

Un ciclu simplu care conține toate vârfurile unui grafic fără repetări este cunoscut sub numele de ciclu hamiltonian .

Ciclul obținut prin adăugarea unei margini a graficului la arborele de întindere al graficului original este cunoscut sub numele de Ciclul Fundamental.

Proprietăți cale

Două căi sunt independente de vârfuri dacă nu împărtășesc vârfuri interioare. În mod similar, două căi sunt independente de margine dacă nu au margini interioare în comun.

Lungimea căii este numărul de muchii utilizate în traseu, marginile reutilizabile fiind numărate de numărul corespunzător de ori. Lungimea poate fi zero dacă calea constă dintr-un singur vârf.

Un grafic ponderat asociază fiecare muchie cu o anumită valoare ( greutatea muchiei ). Greutatea unei căi într-un grafic ponderat este suma greutăților marginilor căii. Uneori, în locul cuvântului greutate preț sau lungime se folosește .

Note

↑ Ore, 2008 , 2.1 Trasee, circuite și circuite simple, p. 34-38.
↑ Wilson, 1977 , Noi definiții, p. 37.
↑ Harari, 2003 , Rute și conectivitate, p. 232.
↑ Harari, 2003 , Digraphs and Connectivity, p. 232.
↑ Christofides, 1978 , Capitolul 1. Introducere 2. Căi și trasee, p. 13.
↑ Bondy, Murty, 1976 .
↑ Gibbons, 1985 .
↑ Distel, 2002 .

Vezi și

Literatură

Harari F. Teoria grafurilor. — M .: URSS , 2003. — 300 p. — ISBN 5-354-00301-6 .
Ore, Oistin . Teoria grafurilor. — M .: URSS , 2008. — 352 p. - ISBN 978-5-397-00044-4 .
N. Christophides. Teoria grafurilor. Abordare algoritmică. - al II-lea .. - M . : Editura „Mir”, 1978.
R. Wilson. Introducere în teoria grafurilor. - M . : Editura „Mir”, 1977. - (Matematică modernă. Cursuri de iniţiere).
JA Bondy, USR Murty. Teoria grafurilor cu aplicații . - Olanda de Nord, 1976. - S. 12-21. — ISBN 0-444-19451-7 .
Reinhard Distel. Teoria grafurilor. - Novosibirsk: Editura Institutului de Matematică, 2002. - ISBN 5-86134-101-X .
Gibbons, A. Teoria graficelor algoritmice. - Cambridge University Press, 1985. - S. 5-6. — ISBN 0-521-28881-9 .
Bernhard Korte, László Lovász, Hans Jürgen Prömel Alexander Schrijver. Căi, fluxuri și VLSI-Layout. - Algoritmi și combinatorică 9, Springer-Verlag, 1990. - ISBN 0-387-52685-4 .

Link -uri

Weisstein, Eric W. Path Graph (engleză) pe site-ul web Wolfram MathWorld .