12. gyakorlat
Gráfok III: fa gráfok
Olyan gráf, amely
- körmentes és
- összefüggő
Tulajdonságok
- Ha \(G\) egy \(n\) csúcsú fa, akkor az éleinek száma \(n-1\)
- \(|E_G| = n - 1\)
- Minden fában van min. 2 elsőfokú csúcs
- \(f_1 \geq c+2\)
- \(f_1\): elsőfokú csúcsok száma
- \(c\): legalább harmadfokú csúcsok száma
Fákkal feladat
Hány csúcsa van egy fának, ha éleinek száma pontosan tizedrésze a komplementerében lévő élek számának?
\(n\) csúcsú fa éleinek száma: \(|E_G|=n-1\)
Komplementerben lévő élek száma: \(|E_{\overline{G}}| = \frac{n(n-1)}{2}-|E_G|\)
Illetve, a feladat leírása szerint:
\[\begin{align*}
|E_G|&=\frac{1}{10}|E_{\overline{G}}| \\
|E_G|&=\frac{1}{10}\left(\frac{n(n-1)}{2}-|E_G|\right) \\
|E_G|&=\frac{n(n-1)}{20}-\frac{1}{10}\cdot|E_G| \\
\frac{11}{10}\cdot|E_G|&=\frac{n(n-1)}{20} \\
|E_G|&=\frac{n(n-1)\cdot10}{20\cdot11} \\
\end{align*}\]
\(n\) csúcsú fa éleinek számáról szóló tétel szerint:
\[\begin{align*}
n-1&=\frac{n(n-1)\cdot10}{20\cdot11} \\
220\cdot(n-1)&=n(n-1)\cdot10 \\
220n-220&=10n^2-10n \\
0&=10n^2-230n+220 \\
0&=n^2-23n+22 \\
n&\in\{22, 1\}
\end{align*}\]
Tehát a fa vagy 1, vagy 22 csúcsú.
Továbbá a gráfokhoz
Euler-vonal
Egy gráfban egy olyan vonalat, amelyben a gráf minden éle szerepel Euler-vonalnak nevezünk. (Az adott gráf élét pontosan egyszer tartalmazza.)
Tételek
Egy összefüggő véges gráfban...
- pontosan akkor van zárt Euler-vonal, ha minden csúcs foka páros.
- pontosan akkor van nyílt Euler-vonal, ha 0 vagy 2 páratlan fokszámú csúcsa van