#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
