# Dvigubo jungumo komponentės [![PDF](../slides_common/img/pdf.png)](./slides.pdf) Parengė Vytautas Strimaitis, PS 4 k.
## Dviryšiai grafai * Dviryšis grafas - tai 2-jungusis grafas. * Apibrėžimas: grafas $G = (V, U)$ yra dviryšis, jei bet kurią viršūnių porą $(a, b), a \neq b$ jungia bent dvi viršūnėmis nesikertančios grandinės. * Kitoks apibrėžimas: grafas $G = (V, U)$ yra dviryšis, jei jis neturi sąlyčio taškų.

Užduotis

Kurie iš duotųjų grafų yra dviryšiai?

Atsakymas

## Dvigubo jungumo komponentės * Dvigubo jungumo komponentė - tai didžiausias galimas grafo $G$ pografis, neturintis sąlyčio taškų. * Dvigubo jungumo komponentės dar vadinamos *blokais*.

Pavyzdys

Nustatyti duoto grafo dvigubo jungumo komponentes.

Atsakymas

## Sąlyčio taško savybė * Neorientuotojo grafo $G$ viršūnė $a$ yra sąlyčio tašku tada ir tik tada, kai egzistuoja tokios dvi grafo viršūnės $x$ ir $y$, kad bet kuris kelias tarp jų eina per viršūnę $a$. * Ši savybė leidžia nesunkiai rasti grafo dvigubo jungumo komponentes pasitelkiant paiešką gilyn.

Dvigubo jungumo komponenčių radimas

  • Pradedame paiešką į gylį nuo bet kurios viršūnės, kuri nėra sąlyčio taškas.
  • Aplankius viršūnę įdedame jos numerį į steką.
  • Po sąlyčio taško $v$ kiekvieno kaimyno aplankymo:
    • Išimame visas viršūnes $u_1, u_2, ..., u_k$ nuo steko viršaus iki viršūnės $v$;
    • Pažymime, kad radome naują dvigubo jungumo komponentę $\{v, u_1, u_2, ..., u_k\}$
  • Pasibaigus paieškos į gylį procedūrai išimame visas likusias viršūnes iš steko ir pažymime, kad tai dar viena nauja dvigubo jungumo komponentė.

Pavyzdys

Pavyzdys

Pavyzdys

1

Pavyzdys

2
1

Pavyzdys

3
2
1

Pavyzdys

4
3
2
1

Pavyzdys

5
4
3
2
1

Pavyzdys

3
2
1
  1. $\{3, 4, 5\}$

Pavyzdys

3
2
1
  1. $\{3, 4, 5\}$

Pavyzdys

6
3
2
1
  1. $\{3, 4, 5\}$

Pavyzdys

7
6
3
2
1
  1. $\{3, 4, 5\}$

Pavyzdys

8
7
6
3
2
1
  1. $\{3, 4, 5\}$

Pavyzdys

9
8
7
6
3
2
1
  1. $\{3, 4, 5\}$

Pavyzdys

10
9
8
7
6
3
2
1
  1. $\{3, 4, 5\}$

Pavyzdys

10
9
8
7
6
3
2
1
  1. $\{3, 4, 5\}$

Pavyzdys

7
6
3
2
1
  1. $\{3, 4, 5\}$
  2. $\{7, 8, 9, 10\}$

Pavyzdys

7
6
3
2
1
  1. $\{3, 4, 5\}$
  2. $\{7, 8, 9, 10\}$

Pavyzdys

3
2
1
  1. $\{3, 4, 5\}$
  2. $\{7, 8, 9, 10\}$
  3. $\{3, 6, 7\}$

Pavyzdys

3
2
1
  1. $\{3, 4, 5\}$
  2. $\{7, 8, 9, 10\}$
  3. $\{3, 6, 7\}$

Pavyzdys

3
2
1
  1. $\{3, 4, 5\}$
  2. $\{7, 8, 9, 10\}$
  3. $\{3, 6, 7\}$

Pavyzdys

  1. $\{3, 4, 5\}$
  2. $\{7, 8, 9, 10\}$
  3. $\{3, 6, 7\}$
  4. $\{1, 2, 3\}$

Užduotis

Raskite duotojo grafo dvigubo jungumo komponentes pasitelkę nagrinėtą algoritmą.