path: root/šola/ds2/kolokvij1.lyx

#LyX 2.3 created this file. For more info see http://www.lyx.org/
\lyxformat 544
\begin_document
\begin_header
\save_transient_properties true
\origin unavailable
\textclass article
\begin_preamble
\usepackage{siunitx}
\usepackage{pgfplots}
\usepackage{listings}
\usepackage{multicol}
\sisetup{output-decimal-marker = {,}, quotient-mode=fraction, output-exponent-marker=\ensuremath{\mathrm{3}}}
\DeclareMathOperator{\g}{g}
\DeclareMathOperator{\sled}{sled}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Cir}{Cir}
\DeclareMathOperator{\ecc}{ecc}
\DeclareMathOperator{\rad}{rad}
\DeclareMathOperator{\diam}{diam}
\newcommand\euler{e}
\end_preamble
\use_default_options true
\begin_modules
enumitem
\end_modules
\maintain_unincluded_children false
\language slovene
\language_package default
\inputencoding auto
\fontencoding global
\font_roman "default" "default"
\font_sans "default" "default"
\font_typewriter "default" "default"
\font_math "auto" "auto"
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100 100
\font_tt_scale 100 100
\use_microtype false
\use_dash_ligatures true
\graphics xetex
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref false
\papersize default
\use_geometry true
\use_package amsmath 1
\use_package amssymb 1
\use_package cancel 1
\use_package esint 1
\use_package mathdots 1
\use_package mathtools 1
\use_package mhchem 1
\use_package stackrel 1
\use_package stmaryrd 1
\use_package undertilde 1
\cite_engine basic
\cite_engine_type default
\biblio_style plain
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\justification false
\use_refstyle 1
\use_minted 0
\index Index
\shortcut idx
\color #008000
\end_index
\leftmargin 1cm
\topmargin 1cm
\rightmargin 1cm
\bottommargin 2cm
\headheight 1cm
\headsep 1cm
\footskip 1cm
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\is_math_indent 0
\math_numbering_side default
\quotes_style german
\dynamic_quotes 0
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
setlength{
\backslash
columnseprule}{0.2pt}
\backslash
begin{multicols}{2}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
Največja stopnja 
\begin_inset Formula $\Delta G$
\end_inset

, najmanjša 
\begin_inset Formula $\delta G$
\end_inset

.
\end_layout

\begin_layout Standard
Rokovanje: 
\begin_inset Formula $\sum_{v\in VG}\deg_{G}v=2\left|EG\right|$
\end_inset

.
\end_layout

\begin_layout Standard
Vsak graf ima sodo mnogo vozlišč lihe stopnje.
\end_layout

\begin_layout Standard
Presek/unija grafov je presek/unija njunih 
\begin_inset Formula $V$
\end_inset

 in 
\begin_inset Formula $E$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $G\cup H$
\end_inset

 je disjunktna unija grafov 
\begin_inset Formula $\sim$
\end_inset

 
\begin_inset Formula $VG\cap VH=\emptyset$
\end_inset

.
\end_layout

\begin_layout Standard
Komplement grafa: 
\begin_inset Formula $\overline{G}$
\end_inset

 (obratna povezanost)
\end_layout

\begin_layout Standard
\begin_inset Formula $0\leq\left|EG\right|\leq{\left|VG\right| \choose 2}\quad\quad\quad$
\end_inset

Za padajoče 
\begin_inset Formula $d_{i}$
\end_inset

 velja:
\end_layout

\begin_layout Standard
\begin_inset Formula $\left(d_{1},\dots d_{n}\right)$
\end_inset

 graf 
\begin_inset Formula $\Leftrightarrow\left(d_{2}-1,\dots,d_{d_{1}+1}-1,\dots,d_{n}\right)$
\end_inset

 graf
\end_layout

\begin_layout Standard
Če je 
\begin_inset Formula $AG$
\end_inset

 matrika sosednosti, 
\begin_inset Formula $\left(\left(AG\right)^{n}\right)_{i,j}$
\end_inset

 pove št.
 
\begin_inset Formula $i,j-$
\end_inset

poti.
\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\text{Število trikotnikov: }\frac{\sled\left(\left(AG\right)^{3}\right)}{2\cdot3}
\]

\end_inset


\end_layout

\begin_layout Paragraph
Sprehod
\end_layout

\begin_layout Standard
je zaporedje vozlišč, ki so verižno povezana.
\end_layout

\begin_layout Standard
Dolžina sprehoda je število prehojenih povezav.
\end_layout

\begin_layout Standard
Sklenjen sprehod dolžine 
\begin_inset Formula $k$
\end_inset

: 
\begin_inset Formula $v_{0}=v_{k}$
\end_inset


\end_layout

\begin_layout Standard
Enostaven sprehod ima disjunktna vozlišča razen 
\begin_inset Formula $\left(v_{0},v_{k}\right)$
\end_inset

.
\end_layout

\begin_layout Standard
Pot v grafu: podgraf 
\begin_inset Formula $P_{k}$
\end_inset

 
\begin_inset Formula $\sim$
\end_inset

 enostaven nesklenjen sprehod.
\end_layout

\begin_layout Paragraph
Cikel
\end_layout

\begin_layout Standard
podgraf, ki je enostaven sklenjen sprehod dolžine 
\begin_inset Formula $>3$
\end_inset

.
\end_layout

\begin_layout Standard
Če v 
\begin_inset Formula $G$
\end_inset

 
\begin_inset Formula $\exists$
\end_inset

 dve različni 
\begin_inset Formula $u,v-$
\end_inset

poti 
\begin_inset Formula $\Leftrightarrow$
\end_inset

 
\begin_inset Formula $G$
\end_inset

 premore cikel
\end_layout

\begin_layout Standard
Sklenjen sprehod lihe dolžine 
\begin_inset Formula $\in G$
\end_inset

 
\begin_inset Formula $\Leftrightarrow$
\end_inset

 lih cikel 
\begin_inset Formula $\in G$
\end_inset


\end_layout

\begin_layout Paragraph
Povezanost
\end_layout

\begin_layout Standard
\begin_inset Formula $u,v$
\end_inset

 sta v isti komponenti 
\begin_inset Formula $\text{\ensuremath{\sim}}$
\end_inset

 
\begin_inset Formula $\text{\ensuremath{\exists}}$
\end_inset

 
\begin_inset Formula $u,v-$
\end_inset

pot
\end_layout

\begin_layout Standard
Število komponent grafa: 
\begin_inset Formula $\Omega G$
\end_inset

.
 
\begin_inset Formula $G$
\end_inset

 povezan 
\begin_inset Formula $\sim\Omega G=1$
\end_inset


\end_layout

\begin_layout Standard
Komponenta je maksimalen povezan podgraf.
\end_layout

\begin_layout Standard
Premer: 
\begin_inset Formula $\diam G=\max\left\{ d_{G}\left(v,u\right);\forall v,u\in VG\right\} $
\end_inset


\end_layout

\begin_layout Standard
Ekscentričnost: 
\begin_inset Formula $\ecc_{G}u=max\left\{ d_{G}\left(u,x\right);\forall x\in VG\right\} $
\end_inset


\end_layout

\begin_layout Standard
Polmer: 
\begin_inset Formula $\rad G=\min\left\{ \ecc u;\forall u\in VG\right\} $
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\diam C_{n}=\rad C_{n}=\lfloor\frac{n}{2}\rfloor$
\end_inset


\end_layout

\begin_layout Standard
(Liha) ožina (
\begin_inset Formula $\g G$
\end_inset

) je dolžina najkrajšega (lihega) cikla.
\end_layout

\begin_layout Standard
Vsaj en od 
\begin_inset Formula $G$
\end_inset

 in 
\begin_inset Formula $\overline{G}$
\end_inset

 je povezan.
\end_layout

\begin_layout Standard
Povezava 
\begin_inset Formula $e$
\end_inset

 je most 
\begin_inset Formula $\Leftrightarrow$
\end_inset

 
\begin_inset Formula $\Omega\left(G-e\right)>\Omega G$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $u$
\end_inset

 je prerezno vozlišče 
\begin_inset Formula $\Leftrightarrow$
\end_inset

 
\begin_inset Formula $\Omega\left(G-u\right)>\Omega G$
\end_inset


\end_layout

\begin_layout Standard
Za nepovezan 
\begin_inset Formula $G$
\end_inset

 velja 
\begin_inset Formula $\diam\overline{G}\leq2$
\end_inset


\end_layout

\begin_layout Paragraph
Dvodelni
\end_layout

\begin_layout Standard
\begin_inset Formula $\sim V=A\cup B,A\cap B=\emptyset,\forall uv\in E:u\in A\oplus v\in A$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $K_{m,n}$
\end_inset

 je poln dvodelni graf, 
\begin_inset Formula $\left|A\right|=m$
\end_inset

, 
\begin_inset Formula $\left|B\right|=n$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 dvodelen 
\begin_inset Formula $\Leftrightarrow\forall$
\end_inset

 komponenta 
\begin_inset Formula $G$
\end_inset

 dvodelna
\end_layout

\begin_layout Standard
Pot, sod cikel, hiperkocka so dvodelni, petersenov ni.
\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 dvodelen 
\begin_inset Formula $\Leftrightarrow G$
\end_inset

 ne vsebuje lihega cikla.
\end_layout

\begin_layout Standard
Biparticija glede na parnost 
\begin_inset Formula $d_{G}\left(u,x_{0}\right)$
\end_inset

, 
\begin_inset Formula $x_{0}$
\end_inset

 fiksen.
\end_layout

\begin_layout Standard
Dvodelen 
\begin_inset Formula $k-$
\end_inset

regularen, 
\begin_inset Formula $\left|E\right|\ge1\Rightarrow$
\end_inset


\begin_inset Formula $\left|A\right|=\left|B\right|$
\end_inset

.
 Dokaz: 
\begin_inset Formula $\sum_{u\in A}\deg u=\left|E\right|=\cancel{k}\left|A\right|=\cancel{k}\left|B\right|=\sum_{u\in B}\deg u$
\end_inset


\end_layout

\begin_layout Paragraph
Krožni
\end_layout

\begin_layout Standard
\begin_inset Formula $\Cir\left(n,\left\{ s_{1},\dots,s_{k}\right\} \right):\left|V\right|=n,$
\end_inset

 množica preskokov
\end_layout

\begin_layout Standard
\begin_inset Formula $\Omega\Cir\left(n,\left\{ s,n-s\right\} \right)=\gcd\left\{ n,s\right\} $
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $W_{n}$
\end_inset

 (kolo) pa je cikel z univerzalnim vozliščem.
\end_layout

\begin_layout Paragraph
Homomorfizem
\end_layout

\begin_layout Standard
\begin_inset Formula $\varphi:VG\to VH$
\end_inset

 slika povezave v povezave
\end_layout

\begin_layout Standard
Primer: 
\begin_inset Formula $K_{2}$
\end_inset

 je homomorfna slika 
\begin_inset Formula $\forall$
\end_inset

 bipartitnega grafa.
\end_layout

\begin_layout Standard
V povezavah in vozliščih surjektiven 
\begin_inset Formula $hm\varphi$
\end_inset

 je epimorfizem.
\end_layout

\begin_layout Standard
V vozliščih injektiven 
\begin_inset Formula $hm\varphi$
\end_inset

 je monomorfizem/vložitev.
\end_layout

\begin_layout Standard
Vložitev, ki ohranja razdalje, je izometrična.
\end_layout

\begin_layout Standard
Kompozitum homomorfizmov je spet homomorfizem.
\end_layout

\begin_layout Standard
Izomorfizem je bijektivni 
\begin_inset Formula $hm\varphi$
\end_inset

 s homomorfnim inverzom.
\end_layout

\begin_layout Standard
\begin_inset Formula $im\varphi$
\end_inset

 
\begin_inset Formula $f:VG\to VH$
\end_inset

 
\begin_inset Formula $\forall u,v\in VG:uv\in EG\Leftrightarrow fufv\in EH$
\end_inset


\end_layout

\begin_layout Standard
Nad množico vseh grafov 
\begin_inset Formula $\mathcal{G}$
\end_inset

 je izomorfizem (
\begin_inset Formula $\cong$
\end_inset

) ekv.
 rel.
\end_layout

\begin_layout Standard
\begin_inset Formula $im\varphi$
\end_inset

 
\begin_inset Formula $G\to G$
\end_inset

 je avtomorfizem.
\end_layout

\begin_layout Standard
\begin_inset Formula $\Aut G$
\end_inset

 je grupa avtomorfizmov s komponiranjem.
\end_layout

\begin_layout Standard
\begin_inset Formula $\Aut K_{n}=\left\{ \pi\in S_{n}=\text{permutacije }n\text{ elementov}\right\} $
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\Aut P_{n}=\left\{ \text{trivialni }id,f\left(i\right)=n-i-1\right\} $
\end_inset

, 
\begin_inset Formula $\Aut G\cong\Aut\overline{G}$
\end_inset


\end_layout

\begin_layout Standard
Izomorfizem ohranja stopnje, št.
 
\begin_inset Formula $C_{4}$
\end_inset

, povezanost, 
\begin_inset Formula $\left|EG\right|,\dots$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $G\cong\overline{G}\Rightarrow\left|VG\right|\%4\in\left\{ 0,1\right\} $
\end_inset


\end_layout

\begin_layout Paragraph
Operacije
\end_layout

\begin_layout Standard
\begin_inset Formula $H$
\end_inset

 vpeti podgraf 
\begin_inset Formula $G\Leftrightarrow\exists F\subseteq EG\ni:H=G-F$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $H$
\end_inset

 inducirani podgraf 
\begin_inset Formula $G\Leftrightarrow\exists S\subseteq VG\ni:H=G-S$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $H$
\end_inset

 podgraf 
\begin_inset Formula $G\Leftrightarrow\exists S\subseteq VG,F\subseteq EG\ni:H=\left(G-F\right)-S$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $uv=e\in EG$
\end_inset

.
 
\begin_inset Formula $G/e$
\end_inset

 je skrčitev.
 (identificiramo 
\begin_inset Formula $u=v$
\end_inset

)
\end_layout

\begin_layout Standard
\begin_inset Formula $H$
\end_inset

 minor 
\begin_inset Formula $G$
\end_inset

: 
\begin_inset Formula $H=f_{1}...f_{k}G$
\end_inset

 za 
\begin_inset Formula $f_{i}$
\end_inset

 skrčitev/odstranjevanje
\end_layout

\begin_layout Standard
\begin_inset Formula $VG^{+}e\coloneqq VG\cup\left\{ x_{e}\right\} $
\end_inset

, 
\begin_inset Formula $EG^{+}e\coloneqq EG\setminus e\cup\left\{ x_{e}u,x_{e}v\right\} $
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $VG^{+}e$
\end_inset

 je subdivizija, 
\begin_inset Formula $e\in EG$
\end_inset

.
 Na 
\begin_inset Formula $e$
\end_inset

 dodamo vozlišče.
\end_layout

\begin_layout Standard
\begin_inset Formula $H$
\end_inset

 subdivizija 
\begin_inset Formula $G$
\end_inset

 
\begin_inset Formula $\Leftrightarrow H=G^{+}\left\{ e_{1},\dots,e_{k}\right\} ^{+}\left\{ f_{1}\dots f_{j}\right\} ^{+}\dots$
\end_inset


\end_layout

\begin_layout Standard
Stopnja vozlišč se s subdivizijo ne poveča.
\end_layout

\begin_layout Standard
Glajenje 
\begin_inset Formula $G^{-}v$
\end_inset

, 
\begin_inset Formula $v\in VG$
\end_inset

 je obrat subdivizije.
 
\begin_inset Formula $\deg_{G}v=2$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 in 
\begin_inset Formula $H$
\end_inset

 sta homeomorfna, če sta subdivizija istega grafa.
\end_layout

\begin_layout Standard
Kartezični produkt: 
\begin_inset Formula $V\left(G\square H\right)\coloneqq VG\times VH$
\end_inset

, 
\begin_inset Formula $E\left(G\square H\right)\coloneqq\left\{ \left\{ \left(g,h\right),\left(g',h'\right)\right\} ;g=g'\wedge hh'\in EH\vee h=h'\wedge gg'\in EG\right\} $
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\left(\mathcal{G},\square\right)$
\end_inset

 monoid, enota 
\begin_inset Formula $K_{1}$
\end_inset

.
 
\begin_inset Formula $Q_{n}\cong Q_{n-1}\square K_{2}=Q_{n-2}\square K_{2}^{\square,2}$
\end_inset


\end_layout

\begin_layout Standard
Disjunktna unija: 
\begin_inset Formula $G$
\end_inset

, 
\begin_inset Formula $H$
\end_inset

 disjunktna.
 
\begin_inset Formula $V\left(G\cup H\right)\coloneqq VG\cup VH$
\end_inset

, 
\begin_inset Formula $E\left(G\cup H\right)\coloneqq EG\cup EH$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $G,H$
\end_inset

 dvodelna 
\begin_inset Formula $\Rightarrow G\square H$
\end_inset

 dvodelen
\end_layout

\begin_layout Paragraph
\begin_inset Formula $k-$
\end_inset

povezan graf
\end_layout

\begin_layout Standard
ima 
\begin_inset Formula $\geq k+1$
\end_inset

 vozlišč in ne vsebuje prerezne množice moči 
\begin_inset Formula $<k$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $X\subseteq VG$
\end_inset

 je prerezna množica 
\begin_inset Formula $\Leftrightarrow\Omega\left(G-X\right)>\Omega G$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $Y\subseteq EG$
\end_inset

 prerezna množica povezav 
\begin_inset Formula $\Leftrightarrow\Omega\left(G-Y\right)>\Omega G$
\end_inset


\end_layout

\begin_layout Standard
Povezanost grafa: 
\begin_inset Formula $\kappa G=\max k$
\end_inset

, da je 
\begin_inset Formula $G$
\end_inset

 
\begin_inset Formula $k-$
\end_inset

povezan.
 Primeri: 
\begin_inset Formula $\kappa K_{n}=n-1$
\end_inset

, 
\begin_inset Formula $\kappa P_{n}=1$
\end_inset

, 
\begin_inset Formula $\kappa C_{n}=2$
\end_inset

, 
\begin_inset Formula $\kappa K_{n,m}=\min\left\{ n,m\right\} $
\end_inset

, 
\begin_inset Formula $\kappa Q_{n}=n$
\end_inset

, 
\begin_inset Formula $\kappa G\text{\ensuremath{\leq}}\delta G$
\end_inset


\end_layout

\begin_layout Standard
Izrek (Menger): 
\begin_inset Formula $\left|VG\right|\geq k+1$
\end_inset

: 
\begin_inset Formula $G$
\end_inset

 
\begin_inset Formula $k-$
\end_inset

povezan 
\begin_inset Formula $\Leftrightarrow\forall u,v\in VG,uv\not\in EG:\exists k$
\end_inset

 notranje disjunktnih 
\begin_inset Formula $u,v-$
\end_inset

poti
\end_layout

\begin_layout Standard
Graf je 
\begin_inset Formula $k-$
\end_inset

povezan po povezavah, če ne vsebuje prerezne množice povezav moči 
\begin_inset Formula $<k$
\end_inset

.
 Povezanost grafa po povezavah: 
\begin_inset Formula $\kappa'G=\max k$
\end_inset

, da je 
\begin_inset Formula $G$
\end_inset

 
\begin_inset Formula $k-$
\end_inset

povezan po povezavah.
 Primeri: 
\begin_inset Formula $\kappa'K_{n}=n-1$
\end_inset

, 
\begin_inset Formula $\kappa'P_{n}=1$
\end_inset

, 
\begin_inset Formula $\kappa'C_{n}=2$
\end_inset


\end_layout

\begin_layout Standard
Izrek (Menger'): 
\begin_inset Formula $G$
\end_inset

 
\begin_inset Formula $k-$
\end_inset

povezan 
\begin_inset Formula $\Leftrightarrow\forall u,v\in VG\exists k$
\end_inset

 po povezavah disjunktnih 
\begin_inset Formula $u,v-$
\end_inset

poti
\end_layout

\begin_layout Standard
\begin_inset Formula $\forall G\in\mathcal{G}:\kappa G\leq\kappa'G\leq\delta G$
\end_inset


\end_layout

\begin_layout Paragraph
Drevo
\end_layout

\begin_layout Standard
je povezan gozd.
 Gozd je graf brez ciklov.
\end_layout

\begin_layout Standard
Drevo z vsaj dvema vozliščema premore dva lista.
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
hspace*{
\backslash
fill}
\end_layout

\end_inset

NTSE:
\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 drevo 
\begin_inset Formula $\Leftrightarrow\forall u,v\in VG\exists!u,v-$
\end_inset

pot 
\begin_inset Formula $\Leftrightarrow\Omega G=1\wedge\forall e\in EG:e$
\end_inset

 most 
\begin_inset Formula $\Leftrightarrow\Omega G=1\wedge\left|EG\right|=\left|VG\right|-1$
\end_inset


\end_layout

\begin_layout Standard
Vpeto drevo grafa je vpet podgraf, ki je drevo.
\end_layout

\begin_layout Standard
\begin_inset Formula $\tau G\sim$
\end_inset

 število vpetih dreves.
 
\begin_inset Formula $\Omega G=1\Leftrightarrow\tau G\geq1$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\forall e\in EG:\tau G=\tau\left(G-e\right)+\tau\left(G/e\right)$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula 
\[
\text{\text{\text{Laplaceova matrika: }}}L\left(G\right)_{ij}=\begin{cases}
\deg_{G}v_{i} & ;i=j\\
-\left(\text{št. uv povezav}\right) & ;\text{drugače}
\end{cases}
\]

\end_inset


\end_layout

\begin_layout Standard
Izrek (Kirchoff): za 
\begin_inset Formula $G$
\end_inset

 povezan multigraf je 
\begin_inset Formula $\forall i:\tau G=\det\left(LG\text{ brez \ensuremath{i}te vrstice in \ensuremath{i}tega stolpca}\right)$
\end_inset

.
 
\begin_inset Formula $\tau K_{n}=n^{n-2}$
\end_inset


\end_layout

\begin_layout Standard
Prüferjeva koda, če lahko linearno uredimo vozlišča: Ponavljaj, dokler 
\begin_inset Formula $VG\not=\emptyset$
\end_inset

: vzemi prvi list, ga odstrani in v vektor dodaj njegovega soseda.
\end_layout

\begin_layout Standard
Blok je maksimalen povezan podgraf brez prereznih vozlišč.
\end_layout

\begin_layout Standard
\begin_inset Formula $\tau G=\tau B_{1}\cdot\cdots\cdot\tau B_{k}$
\end_inset

 za bloke 
\begin_inset Formula $\vec{B}$
\end_inset

 grafa 
\begin_inset Formula $G$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{multicols}
\end_layout

\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
begin{multicols}{2}
\end_layout

\end_inset


\end_layout

\begin_layout Paragraph
Eulerjev
\end_layout

\begin_layout Standard
sprehod v m.grafu vsebuje vse povezave po enkrat.
\end_layout

\begin_layout Standard
Eulerjev obhod je sklenjen eulerjev sprehod.
\end_layout

\begin_layout Standard
Eulerjev graf premore eulerjev obhod.
\end_layout

\begin_layout Standard
Za povezan multigraf 
\begin_inset Formula $G$
\end_inset

 eulerjev 
\begin_inset Formula $\Leftrightarrow\forall v\in VG:\deg_{G}v$
\end_inset

 sod
\end_layout

\begin_layout Standard
Fleuryjev algoritem za eulerjev obhod v eulerjevem grafu: Začnemo v poljubni
 povezavi, jo izbrišemo, nadaljujemo na mostu le, če nimamo druge možne
 povezave.
\end_layout

\begin_layout Standard
Dekompozicija: delitev na povezavno disjunktne podgrafe.
\end_layout

\begin_layout Standard
Dekompozicija je lepa, če so podgrafi izomorfni.
 (
\begin_inset Formula $\exists$
\end_inset

 za 
\begin_inset Formula $P_{5,2}$
\end_inset

)
\end_layout

\begin_layout Standard
Vsak eulerjev graf premore dekompozicijo v cikle.
\end_layout

\begin_layout Standard
\begin_inset Formula $Q_{n}$
\end_inset

 eulerjev 
\begin_inset Formula $\Leftrightarrow n$
\end_inset

 sod
\end_layout

\begin_layout Standard
\begin_inset Formula $K_{m,n,p}$
\end_inset

 eulerjev 
\begin_inset Formula $\Leftrightarrow m,n,p$
\end_inset

 iste parnosti
\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 eulerjev 
\begin_inset Formula $\wedge H$
\end_inset

 eulerjev 
\begin_inset Formula $\Rightarrow G\square H$
\end_inset

 eulerjev
\end_layout

\begin_layout Paragraph
Hamiltonov
\end_layout

\begin_layout Standard
cikel vsebuje vsa vozlišča grafa.
\end_layout

\begin_layout Standard
Hamilton graf premore Hamiltonov cikel.
\end_layout

\begin_layout Standard
Hamiltonova pot vsebuje vsa vozlišča.
\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 hamiltonov, 
\begin_inset Formula $S\subseteq VG\Rightarrow\Omega\left(G-S\right)\leq\left|S\right|$
\end_inset

 torej:
\end_layout

\begin_layout Standard
\begin_inset Formula $\exists S\in VG:\Omega\left(G-S\right)>\left|S\right|\Rightarrow G$
\end_inset

 ni hamiltonov.
 Primer: 
\begin_inset Formula $G$
\end_inset

 vsebuje prerezno vozlišče 
\begin_inset Formula $\Rightarrow G$
\end_inset

 ni hamiltonov.
\end_layout

\begin_layout Standard
\begin_inset Formula $K_{n,m}$
\end_inset

 je hamiltonov 
\begin_inset Formula $\Leftrightarrow m=n$
\end_inset

 (za 
\begin_inset Formula $S$
\end_inset

 vzamemo 
\begin_inset Formula $\min\left\{ m,n\right\} $
\end_inset

)
\end_layout

\begin_layout Standard
\begin_inset Formula $\left|VG\right|\geq3,\forall u,v\in VG:\deg_{G}u+\deg_{G}v\geq\left|VG\right|\Rightarrow G$
\end_inset

 hamil.
\end_layout

\begin_layout Standard
Dirac: 
\begin_inset Formula $\left|VG\right|\geq3,\forall u\in VG:\deg_{G}u\geq\frac{\left|VG\right|}{2}\Rightarrow G$
\end_inset

 hamilton.
\end_layout

\begin_layout Paragraph
Ravninski
\end_layout

\begin_layout Standard
graf brez sekanja povezav narišemo v ravnino
\end_layout

\begin_layout Standard
\begin_inset Formula $K_{2,3}$
\end_inset

 je ravninski, 
\begin_inset Formula $K_{3,3}$
\end_inset

, 
\begin_inset Formula $K_{5}$
\end_inset

, 
\begin_inset Formula $C_{5}\square C_{5}$
\end_inset

 in 
\begin_inset Formula $P_{5,2}$
\end_inset

 niso ravninski.
\end_layout

\begin_layout Standard
Vložitev je ravninski graf z ustrezno risbo v ravnini.
\end_layout

\begin_layout Standard
Lica so sklenjena območja vložitve brez vozlišč in povezav.
\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 lahko vložimo v ravnino 
\begin_inset Formula $\Leftrightarrow G$
\end_inset

 lahko vložimo na sfero.
\end_layout

\begin_layout Standard
Dolžina lica 
\begin_inset Formula $F\sim lF$
\end_inset

 je št.
 povezav obhoda lica.
\end_layout

\begin_layout Standard
Drevo je ravninski graf z enim licem dolžine 
\begin_inset Formula $2\left|ET\right|$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $\sum_{F\in FG}lF=2\left|EG\right|$
\end_inset

, 
\begin_inset Formula $lF\geq gG$
\end_inset

 za ravninski 
\begin_inset Formula $G$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $2\left|EG\right|=\sum_{F\in FG}lF\geq\sum_{F\in FG}gG=gG\left|FG\right|$
\end_inset

 (
\begin_inset Formula $G$
\end_inset

 ravn.)
\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 ravninski 
\begin_inset Formula $\Rightarrow\left|EG\right|\geq\frac{gG}{2}$
\end_inset


\begin_inset Formula $\left|FG\right|$
\end_inset


\end_layout

\begin_layout Standard
Euler: 
\begin_inset Formula $\left|VG\right|-\left|EG\right|+\left|FG\right|=1+\Omega G$
\end_inset

 za ravninski 
\begin_inset Formula $G$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 ravninski, 
\begin_inset Formula $\left|VG\right|\geq3\Rightarrow\left|EG\right|\leq3\left|VG\right|-6$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 ravninski brez 
\begin_inset Formula $C_{3}$
\end_inset

, 
\begin_inset Formula $\left|VG\right|\geq3\Rightarrow\left|EG\right|\text{\ensuremath{\leq2\left|VG\right|-4}}$
\end_inset


\end_layout

\begin_layout Standard
Triangulacija je taka vložitev, da so vsa lica omejena s 
\begin_inset Formula $C_{3}$
\end_inset

.
\end_layout

\begin_layout Standard
V maksimalen ravninski graf ne moremo dodati povezave, da bi ostal ravninski.
 
\begin_inset Formula $\sim$
\end_inset

 Ni pravi vpet podgraf ravn.
 grafa.
\end_layout

\begin_layout Standard
\begin_inset Formula $K_{5}-e$
\end_inset

 je maksimalen ravninski graf 
\begin_inset Formula $\forall e\in EK_{5}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 ravninski.
 NTSE: 
\begin_inset Formula $G$
\end_inset

 triangulacija 
\begin_inset Formula $\Leftrightarrow G$
\end_inset

 maksimalen ravninski 
\begin_inset Formula $\Leftrightarrow\left|EG\right|=3\left|VG\right|-6$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset Formula $G$
\end_inset

 ravninski 
\begin_inset Formula $\Leftrightarrow$
\end_inset

 vsaka subdivizija 
\begin_inset Formula $G$
\end_inset

 ravninska.
\end_layout

\begin_layout Standard
Kuratovski: 
\begin_inset Formula $G$
\end_inset

 ravn.
 
\begin_inset Formula $\Leftrightarrow$
\end_inset

 ne vsebuje subdivizije 
\begin_inset Formula $K_{5}$
\end_inset

 ali 
\begin_inset Formula $K_{3,3}$
\end_inset


\end_layout

\begin_layout Standard
Wagner: 
\begin_inset Formula $G$
\end_inset

 ravn.
 
\begin_inset Formula $\Leftrightarrow$
\end_inset

 niti 
\begin_inset Formula $K_{5}$
\end_inset

 niti 
\begin_inset Formula $K_{3,3}$
\end_inset

 nista njegova minorja
\end_layout

\begin_layout Standard
Zunanje-ravninski ima vsa vozlišča na robu zunanjega lica.
\end_layout

\begin_layout Standard
\begin_inset Formula $2-$
\end_inset

povezan zunanje-ravninski je 
\series bold
hamiltonov
\series default
.
\end_layout

\begin_layout Standard
Zunanje-ravninski 
\begin_inset Formula $G$
\end_inset

, 
\begin_inset Formula $\left|VG\right|\geq2$
\end_inset

 ima vozlišče stopnje 
\begin_inset Formula $\leq2$
\end_inset

.
\end_layout

\begin_layout Paragraph
Barvanje
\end_layout

\begin_layout Standard
je taka 
\begin_inset Formula $C:VG\to\left\{ 1..k\right\} \Leftrightarrow\forall uv\in EG:Cu\not=Cv$
\end_inset


\end_layout

\begin_layout Standard
Kromatično število 
\begin_inset Formula $\chi G$
\end_inset

 je najmanjši 
\begin_inset Formula $k$
\end_inset

, 
\begin_inset Formula $\ni:\exists$
\end_inset

 
\begin_inset Formula $k-$
\end_inset

barvanje 
\begin_inset Formula $G$
\end_inset


\end_layout

\begin_layout Standard
Primer: 
\begin_inset Formula $\chi K_{n}=n$
\end_inset

, 
\begin_inset Formula $\chi C_{n}=\begin{cases}
2 & ;n\text{ sod}\\
3 & ;n\text{ lih}
\end{cases}$
\end_inset


\end_layout

\begin_layout Standard
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
end{multicols}
\end_layout

\end_inset


\end_layout

\end_body
\end_document