Lanț elementar și ciclu la BAC: exemple pe graf

Un lanț într-un graf neorientat este o succesiune de vârfuri în care fiecare două vârfuri consecutive sunt unite printr-o muchie. La BAC, verificarea trebuie făcută în această ordine: existența muchiilor, apoi eventualele repetări și închiderea traseului. O listă de etichete distincte nu este automat un lanț.

Lecția privește grafurile simple neorientate de la matematică-informatică. Vom deosebi lanțul elementar de ciclul elementar prin exemple construite pe aceeași listă de muchii. Folosește definițiile din enunțul unui subiect de BAC, mai ales dacă apar termeni suplimentari despre repetarea muchiilor.

Graful de lucru

Luăm vârfurile unu, doi, trei, patru, cinci și șase. Muchiile sunt între unu și doi, doi și trei, trei și unu, trei și patru, patru și cinci. Vârful șase este izolat.

Primele trei vârfuri formează un triunghi. Din vârful trei continuă o legătură spre patru și apoi spre cinci. Această descriere este completă: nu presupunem alte muchii doar fiindcă două vârfuri ar putea fi desenate aproape unul de altul.

Vârf	Vecini
1	2, 3
2	1, 3
3	1, 2, 4
4	3, 5
5	4
6	Niciunul

Tabelul vecinilor poate înlocui desenul în verificarea succesiunilor. Pentru fiecare pas, cauți următorul vârf în lista vecinilor celui curent. Astfel, aspectul geometric al unei schițe nu influențează răspunsul.

Verifică mai întâi dacă succesiunea este lanț

Succesiunea unu, trei, patru, cinci este lanț: există muchiile dintre unu și trei, trei și patru, patru și cinci. Succesiunea unu, doi, patru, cinci nu este lanț, deoarece lipsește muchia dintre doi și patru.

Nu este suficient ca toate vârfurile să aparțină aceleiași componente conexe. În exemplul respins, doi și patru pot fi conectate prin vârful trei, dar acel vârf intermediar nu apare în succesiunea propusă. Fiecare pas scris trebuie să fie o muchie directă.

Pentru un graf neorientat, un lanț poate fi parcurs și în sens invers. Succesiunea cinci, patru, trei, unu este validă dacă unu, trei, patru, cinci este validă. Această proprietate nu se transferă automat grafurilor orientate.

Ce înseamnă lanț elementar

Un lanț este elementar dacă vârfurile sale sunt distincte. Succesiunea unu, trei, patru, cinci este elementară, deoarece fiecare vârf apare o singură dată.

Succesiunea unu, doi, trei, unu, trei, patru este un lanț în sensul general folosit aici: toate trecerile sunt muchii ale grafului. Nu este însă elementar, deoarece vârfurile unu și trei se repetă.

Proprietatea elementară se verifică numai după ce ai confirmat că succesiunea este lanț. Pentru lista unu, doi, patru, cinci, lipsa repetărilor nu repară muchia absentă. Ea rămâne o succesiune invalidă ca lanț.

Lungimea numără muchiile parcurse

Un lanț scris prin patru vârfuri are trei treceri, deci lungimea trei. În general, numărul trecerilor este cu unu mai mic decât numărul termenilor din succesiunea scrisă.

Lungimea nu este numărul vârfurilor distincte în cazul unui lanț cu repetări. Succesiunea unu, doi, trei, unu are trei treceri și lungimea trei, deși prima etichetă apare din nou la final.

Pentru un lanț elementar între două vârfuri distincte, toate vârfurile sunt diferite, iar relația dintre lungime și numărul vârfurilor este imediată. Un lanț cu un singur vârf poate fi considerat de lungime zero; precizează convenția dacă aceasta contează în problemă.

Ciclul elementar

Un ciclu elementar într-un graf simplu neorientat revine la vârful inițial, are cel puțin trei muchii și nu repetă alte vârfuri. Succesiunea unu, doi, trei, unu descrie un asemenea ciclu în graful nostru.

Primul și ultimul termen coincid pentru a arăta închiderea. Această repetare este necesară în scrierea ciclului și nu trebuie confundată cu repetarea unui vârf interior. Vârfurile distincte ale ciclului sunt unu, doi și trei.

Succesiunea unu, doi, unu nu este un ciclu elementar al unui graf simplu neorientat. Ea parcurge aceeași muchie la dus și la întors și are numai două treceri. Nu creează un ciclu nou doar prin revenirea la început.

Aceeași figură, mai multe scrieri

Ciclul unu, doi, trei, unu poate fi scris începând din doi: doi, trei, unu, doi. Poate fi parcurs și invers: unu, trei, doi, unu. Aceste scrieri descriu același ciclu neorientat, nu trei cicluri diferite.

La o problemă de numărare, trebuie să știi dacă se numără ciclurile ca substructuri sau succesiunile de etichete cu început și sens fixate. Numerele pot diferi, deoarece aceeași substructură are mai multe reprezentări.

Nu dubla sau tripla un rezultat doar pentru că ai redesenat ciclul ori ai schimbat vârful de început. Identifică mai întâi obiectul pe care îl numără enunțul.

Lanț între două vârfuri și conexitate

Vârfurile unu și cinci sunt conectate prin lanțul unu, trei, patru, cinci. Vârfurile doi și cinci sunt conectate prin doi, trei, patru, cinci. Vârful șase nu este conectat cu niciunul dintre celelalte, fiind izolat.

Existența unui lanț între o anumită pereche nu dovedește conexitatea întregului graf. Pentru conexitate, orice două vârfuri trebuie să poată fi unite printr-un lanț. În graful nostru, vârful șase oferă un contraexemplu.

Dacă există un lanț cu repetări între două vârfuri, poți elimina porțiunile închise inutile până obții un lanț elementar între aceleași capete. Pentru verificarea accesibilității nu este necesar să păstrezi ocolurile care revin la un vârf deja vizitat.

Tabel de clasificare

Succesiune	Verdict	Motiv
1, 3, 4, 5	Lanț elementar	Toate muchiile există, vârfurile sunt distincte
1, 2, 4, 5	Nu este lanț	Lipsește muchia dintre 2 și 4
1, 2, 3, 1	Ciclu elementar	Se închide după trei muchii, fără repetări interioare
1, 2, 1	Lanț neelementar, nu ciclu elementar	Repetă vârful 1 și aceeași muchie
6, 1	Nu este lanț	Vârful 6 este izolat

Tabelul păstrează separat validitatea trecerilor și proprietățile suplimentare. Această ordine de verificare ajută la înțelegerea definițiilor și previne răspunsurile bazate doar pe forma listei.

Exerciții cu răspunsuri

Ce lungime are lanțul doi, unu, trei, patru? Are lungimea trei și este elementar. Toate cele trei muchii necesare există.

Poate vârful cinci să aparțină unui ciclu elementar din acest graf? Nu. Are un singur vecin, iar un ciclu elementar ar avea nevoie de două muchii distincte incidente lui.

Adăugăm muchia dintre cinci și unu. Apare ciclul elementar unu, trei, patru, cinci, unu. Are lungimea patru, iar noua muchie permite închiderea.

Eliminăm muchia dintre unu și doi. Triunghiul inițial nu mai este ciclu, dar unu și doi rămân conectate prin vârful trei. Dispariția unui ciclu nu înseamnă automat separarea componentelor.

Întrebări frecvente

Orice succesiune fără repetări este lanț elementar?

Nu. Trebuie să existe mai întâi toate muchiile dintre vârfurile consecutive. Absența repetărilor verifică doar caracterul elementar al unui lanț deja valid.

Un lanț elementar poate reveni la vârful inițial?

În definiția folosită, vârfurile unui lanț elementar sunt distincte. Pentru o succesiune închisă folosim separat noțiunea de ciclu elementar, care permite repetarea capătului pentru închidere.

Cum verific dacă desenul mă induce în eroare?

Scrie lista muchiilor sau tabelul vecinilor și controlează fiecare trecere. Pentru corectarea unei clasificări, poți consulta un profesor de informatică.