summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--šola/ds2/kolokvij2.lyx3368
-rw-r--r--šola/ds2/teor.lyx7562
2 files changed, 10930 insertions, 0 deletions
diff --git a/šola/ds2/kolokvij2.lyx b/šola/ds2/kolokvij2.lyx
new file mode 100644
index 0000000..0d2e149
--- /dev/null
+++ b/šola/ds2/kolokvij2.lyx
@@ -0,0 +1,3368 @@
+#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 Standard
+\begin_inset Formula $\left|EK_{n}\right|={n \choose 2}$
+\end_inset
+
+,
+\begin_inset Formula ${n \choose k}=\frac{n!}{k!\left(n-k\right)!}$
+\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 vozlišč
+\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
+\begin_inset Formula $\chi C_{n}=\begin{cases}
+2 & ;n\text{ sod}\\
+3 & ;n\text{ lih}
+\end{cases}$
+\end_inset
+
+,
+\begin_inset Formula $\chi G\leq\left|VG\right|,\chi G=\left|VG\right|\Leftrightarrow G\cong K_{n}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $H$
+\end_inset
+
+ podgraf
+\begin_inset Formula $G\Rightarrow\chi G\geq\chi H$
+\end_inset
+
+.
+
+\begin_inset Formula $\chi\text{bipartitni}=2$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Barvni razred so vsa vozlišča iste barve.
+ Je brez povezav
+\begin_inset Formula $\sim$
+\end_inset
+
+
+\series bold
+neodvisna množica
+\series default
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\chi G=k\Leftrightarrow\chi G\leq k\wedge\chi G\geq k$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Klično št.:
+\begin_inset Formula $\omega G\coloneqq$
+\end_inset
+
+
+\begin_inset Formula $\left|V\right|$
+\end_inset
+
+ najv.
+ polnega podgr.
+ v
+\begin_inset Formula $G$
+\end_inset
+
+.
+
+\begin_inset Formula $\omega G\leq\chi G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Trditev:
+\begin_inset Formula $\forall n\in\mathbb{N}\exists G\in\mathcal{G}\ni:\omega G=2\wedge\chi G=n$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Požrešno barvanje: Vozlišča v poljubnem vrstnem redu barvamo z najnižno
+ možno barvo.
+\end_layout
+
+\begin_layout Standard
+Vedno
+\begin_inset Formula $\exists$
+\end_inset
+
+ vrstni red, ki vrne barvanje s
+\begin_inset Formula $\chi G$
+\end_inset
+
+ barvami.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\forall G\in\mathcal{G}:\chi G\leq\Delta G+1$
+\end_inset
+
+, če
+\begin_inset Formula $G$
+\end_inset
+
+ ni regularen celo
+\begin_inset Formula $\chi G\leq\Delta G$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Brooks:
+\begin_inset Formula $G$
+\end_inset
+
+ povezan,
+\begin_inset Formula $G$
+\end_inset
+
+ ni poln niti lihi cikel
+\begin_inset Formula $\Rightarrow\chi G\leq\Delta G$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+let
+\begin_inset Formula $d_{1}\geq\cdots\geq d_{n}$
+\end_inset
+
+ stopnje.
+
+\begin_inset Formula $\chi G=1+\max_{i=1}^{n}\min\left\{ d_{i},i-1\right\} $
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Spoj
+\begin_inset Formula $G\oplus H$
+\end_inset
+
+ je disjunktna unija
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $H$
+\end_inset
+
+ z vsemi pov.
+ med njima
+\end_layout
+
+\begin_layout Standard
+Disjunktna unija je unija brez preseka.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\chi\left(G\oplus H\right)=\chi G+\chi H$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Ravninski graf ima
+\begin_inset Formula $\chi G\leq4$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Paragraph
+Barvanje povezav
+\end_layout
+
+\begin_layout Standard
+Povezavi s skupnim vozl.
+
+\begin_inset Formula $\Rightarrow$
+\end_inset
+
+ razl.
+ barvi.
+\end_layout
+
+\begin_layout Standard
+Kromatični indeks
+\begin_inset Formula $\chi'G$
+\end_inset
+
+ je najm.
+ št.
+ barv za barv.
+ pov.
+
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\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
+Vizing:
+\begin_inset Formula $\forall G\in\mathcal{G}:\Delta G\geq\chi'G\geq\Delta G+1$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\chi G\in\left\{ \Delta G\text{ razred I.},\Delta G+1\text{ razred II.}\right\} $
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $K_{2k+1}\in$
+\end_inset
+
+ II.,
+\begin_inset Formula $K_{2k}\in$
+\end_inset
+
+ I., bipartitni
+\begin_inset Formula $\in$
+\end_inset
+
+ I.
+\end_layout
+
+\begin_layout Paragraph
+Neodvisne množice
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $I\subseteq VG$
+\end_inset
+
+ je neodvisna, če je podgraf, induciran z
+\begin_inset Formula $I$
+\end_inset
+
+, brez povezav.
+\end_layout
+
+\begin_layout Standard
+Neodvisnostno št
+\begin_inset Formula $\alpha G$
+\end_inset
+
+ je moč največje neodvisne množice.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\alpha K_{n}=1$
+\end_inset
+
+,
+\begin_inset Formula $\alpha C_{n}=\lfloor\frac{n}{2}\rfloor$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\alpha G\leq\sum_{i=1}^{k}\alpha H_{i}$
+\end_inset
+
+, kjer so
+\begin_inset Formula $H_{i}$
+\end_inset
+
+ disjunktni inducirani podgr.
+
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\forall G\in\mathcal{G}:\alpha G\cdot\chi G\geq\left|VG\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\frac{\left|VG\right|}{\chi G}\leq\alpha G\leq\left|VG\right|-\frac{\left|EG\right|}{\Delta G}$
+\end_inset
+
+ — zgornja in spodnja meja.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $Iu$
+\end_inset
+
+ je
+\begin_inset Formula $\alpha$
+\end_inset
+
+ poddrevesa s korenom
+\begin_inset Formula $u$
+\end_inset
+
+ v
+\begin_inset Formula $T$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\alpha T=Ir=\max\left\{ 1+\sum_{u\text{ sinovi }r}Iu,\sum_{u\text{ vnuki }r}Iu\right\} $
+\end_inset
+
+
+\end_layout
+
+\begin_layout Paragraph
+Dominantne množice
+\end_layout
+
+\begin_layout Standard
+Neodvisna
+\begin_inset Formula $I\subseteq G$
+\end_inset
+
+ je maksimalna
+\begin_inset Formula $\sim\nexists S\text{ neodvisna}\subseteq G\ni:I\subset S\sim$
+\end_inset
+
+ ni prava
+\begin_inset Formula $\subset$
+\end_inset
+
+ neodv.
+ mn.
+\end_layout
+
+\begin_layout Standard
+Dominantna množica je maksimalna neodvisna, kjer ima vsako vozlišče iz
+\begin_inset Formula $G\setminus I$
+\end_inset
+
+ soseda v
+\begin_inset Formula $I$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $D\subseteq VG$
+\end_inset
+
+ dominira
+\begin_inset Formula $X\subseteq VG$
+\end_inset
+
+, če je vsako vozlišče iz
+\begin_inset Formula $X$
+\end_inset
+
+ v
+\begin_inset Formula $D$
+\end_inset
+
+ ali pa ima soseda v
+\begin_inset Formula $D$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $N_{G}\left(u\right)=$
+\end_inset
+
+sosedje
+\begin_inset Formula $u$
+\end_inset
+
+ v
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $N_{G}\left[u\right]=N_{G}\left(u\right)\cup\left\{ u\right\} $
+\end_inset
+
+ zap.
+ sos.
+
+\begin_inset Formula $u$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $N_{G}\left[D\right]=\bigcup_{u\in D}N_{G}\left[u\right]$
+\end_inset
+
+ zaprta soseščina množice
+\begin_inset Formula $D$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $D$
+\end_inset
+
+ dominira
+\begin_inset Formula $X\sim X\subseteq N_{G}\left[D\right]$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $D$
+\end_inset
+
+ dominira
+\begin_inset Formula $VG\sim D$
+\end_inset
+
+ dominantna množica
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Dominacijsko število
+\begin_inset Formula $\gamma G=$
+\end_inset
+
+ moč največje dom.
+ mn.
+\end_layout
+
+\begin_layout Standard
+Vsaka maksimalna neodvisna mn.
+
+\begin_inset Formula $G$
+\end_inset
+
+ je dom.
+ mn.
+
+\begin_inset Formula $G$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\gamma K_{n}=1$
+\end_inset
+
+,
+\begin_inset Formula $\gamma C_{n}=\lceil\frac{n}{3}\rceil$
+\end_inset
+
+,
+\begin_inset Formula $\gamma P=3$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Za vsak graf brez izoliranih vozlišč
+\begin_inset Formula $\lceil\frac{\left|VG\right|}{\Delta G+1}\rceil\leq\gamma G\leq\lfloor\frac{\left|VG\right|}{2}\rfloor$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $X$
+\end_inset
+
+ je 2-pakiranje
+\begin_inset Formula $G$
+\end_inset
+
+, če
+\begin_inset Formula $\forall x,y\in X:x\not=y\Rightarrow d_{G}\left(x,y\right)\geq3$
+\end_inset
+
+ zdb
+\begin_inset Formula $\forall x,y\in X:x\not=y\Rightarrow N_{G}x\cap N_{G}y=\emptyset$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Moč največjega 2-pakiranja je 2-pakirno število
+\begin_inset Formula $\rho G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $G$
+\end_inset
+
+ povezan
+\begin_inset Formula $\Rightarrow\gamma G\geq\rho G$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Dominantna
+\begin_inset Formula $X$
+\end_inset
+
+ je popolna koda
+\begin_inset Formula $G\Leftrightarrow\bigcup_{u\in X}N_{G}\left[u\right]=VG$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Če graf premore popolno kodo
+\begin_inset Formula $\Rightarrow\gamma G=\rho G$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $H$
+\end_inset
+
+ vpet podgraf
+\begin_inset Formula $G\Rightarrow\gamma G\leq\gamma H$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Povezan
+\begin_inset Formula $G$
+\end_inset
+
+ premore vpeto drevo
+\begin_inset Formula $T\ni:\gamma G=\gamma T$
+\end_inset
+
+.
+ Dokaz: odstrani vse povezave, kjer
+\begin_inset Formula $G-e$
+\end_inset
+
+ ohrani
+\begin_inset Formula $\gamma$
+\end_inset
+
+ in povezanost.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left|VG\right|\geq1\Rightarrow\gamma G\leq\chi\overline{G}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Povezana dom.
+ mn.
+ inducira povez.
+ podgraf.
+ —
+\begin_inset Formula $\gamma_{c}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Neodvisna dom.
+ mn.
+ inducira podgraf brez povezav —
+\begin_inset Formula $\gamma_{i}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $X$
+\end_inset
+
+ je celotna dom.
+ mn.
+
+\begin_inset Formula $\Leftrightarrow\forall v\in VG:N_{G}\left(v\right)\cap X\not=\emptyset$
+\end_inset
+
+ —
+\begin_inset Formula $\gamma_{t}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $G$
+\end_inset
+
+ brez izol.
+ vozl.:
+\begin_inset Formula $\gamma G\leq\gamma_{t}G\leq2\gamma G$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Paragraph
+Algebrske strukture z eno operacijo
+\end_layout
+
+\begin_layout Standard
+Grupoid: notranjost, polgrupa: asociativen grupoid, monoid: polgrupa z enoto
+\end_layout
+
+\begin_layout Standard
+Grupa:
+\begin_inset Formula $\forall a\in A\exists a^{-1}\in A\ni:a\cdot a^{-1}=a^{-1}\cdot a=e$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Potence v monoidu:
+\begin_inset Formula $n\in\mathbb{N}_{0}$
+\end_inset
+
+.
+
+\begin_inset Formula $a^{0}=e$
+\end_inset
+
+,
+\begin_inset Formula $a^{n}=a\cdot a^{n-1}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left(a\cdot b\right)^{-1}=b^{-1}\cdot a^{-1}$
+\end_inset
+
+,
+\begin_inset Formula $a^{n}\cdot a^{m}=a^{n+m},\left(a^{n}\right)^{m}=a^{nm}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left(a^{-1}\right)^{n}=\left(a^{n}\right)^{-1}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left(\mathbb{Z}_{m},+_{m}\right)$
+\end_inset
+
+ grupa,
+\begin_inset Formula $\left(\mathbb{Z}_{m},\cdot_{n}\right)$
+\end_inset
+
+ monoid
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $k\in\mathbb{Z}_{n}$
+\end_inset
+
+ obrnljiv v
+\begin_inset Formula $\left(\mathbb{Z}_{n},\cdot_{n}\right)\Leftrightarrow k\perp n\sim\gcd\left\{ k,n\right\} =1$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Komutativni grupi pravimo abelova.
+\end_layout
+
+\begin_layout Standard
+Cayleyeva tabela je predpis za grupoid
+\begin_inset Formula $\cdot:A^{2}\to A$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+red
+\begin_inset Formula $a$
+\end_inset
+
+ je najmanjši
+\begin_inset Formula $n\in\mathbb{N}\ni:a^{n}=e$
+\end_inset
+
+ oz.
+
+\begin_inset Formula $\infty$
+\end_inset
+
+, če ne obstaja.
+\end_layout
+
+\begin_layout Standard
+Def.:
+\begin_inset Formula $H\subseteq G$
+\end_inset
+
+ podgrupa, če je grupa za isto operacijo.
+\end_layout
+
+\begin_layout Standard
+Izrek:
+\begin_inset Formula $H\subseteq G$
+\end_inset
+
+ podgrupa
+\begin_inset Formula $\Leftrightarrow\forall x,y\in H:x^{-1}y\in H$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Trivialni podgrupi
+\begin_inset Formula $G$
+\end_inset
+
+ sta
+\begin_inset Formula $\left\{ e\right\} $
+\end_inset
+
+ in
+\begin_inset Formula $G$
+\end_inset
+
+.
+
+\begin_inset space \hfill{}
+\end_inset
+
+Ciklična podgrupa:
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left\langle a\right\rangle \coloneqq\left\{ a^{n};\forall n\in\mathbb{Z}\right\} $
+\end_inset
+
+ je podgrupa v
+\begin_inset Formula $G$
+\end_inset
+
+ za
+\begin_inset Formula $a\in\text{grupa }G$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Center grupe:
+\begin_inset Formula $ZG=\left\{ a\in G;\forall x\in G:ax=xa\right\} $
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left(ZG,\cdot\right)$
+\end_inset
+
+je podgrupa grupe
+\begin_inset Formula $\left(G,\cdot\right)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Paragraph
+Permutacijske grupe
+\end_layout
+
+\begin_layout Standard
+Permutacija je bijekcija
+\begin_inset Formula $A\to A$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+perm.
+ gr.
+ so permutacije
+\begin_inset Formula $A$
+\end_inset
+
+, ki tvorijo grupo za
+\begin_inset Formula $\circ$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Polna simetrična grupa
+\begin_inset Formula $S_{n}\coloneqq\left\{ \pi:\left\{ 1..n\right\} \to\left\{ 1..n\right\} ;\pi\text{ bijekcija}\right\} $
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Alternirajoča grupa
+\begin_inset Formula $A_{n}\coloneqq\left\{ \pi\in S_{n};\pi\text{ soda}\right\} $
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Permutacija kot produkt disjunktnih ciklov dolžin
+\begin_inset Formula $l_{1},\dots,l_{n}$
+\end_inset
+
+ je soda, če je
+\begin_inset Formula $\left(l_{1}-1\right)+\cdots+\left(l_{n}-1\right)$
+\end_inset
+
+ sod.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left|S_{n}\right|=n!$
+\end_inset
+
+,
+\begin_inset Formula $\left|A_{n}\right|=\frac{n!}{2}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left(G,\circ\right)$
+\end_inset
+
+,
+\begin_inset Formula $\left(H,*\right)$
+\end_inset
+
+ grupi.
+
+\begin_inset Formula $f:G\to H$
+\end_inset
+
+ je hm
+\begin_inset Formula $\varphi\Leftrightarrow\forall x,y\in G:f\left(x\circ y\right)=fx*fy$
+\end_inset
+
+.
+
+\begin_inset Formula $f$
+\end_inset
+
+ je še celo im
+\begin_inset Formula $\varphi\Leftrightarrow f$
+\end_inset
+
+ bijekcija.
+\end_layout
+
+\begin_layout Standard
+Grupi sta izomorfni
+\begin_inset Formula $\sim\text{\ensuremath{\exists}}$
+\end_inset
+
+im
+\begin_inset Formula $\varphi$
+\end_inset
+
+ med njima:
+\begin_inset Formula $G\approx H$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Vsaka grupa je izomorfna neki permutacijski grupi
+\end_layout
+
+\begin_layout Paragraph
+Odseki in podgrupe edinke
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left(G,\circ\right)$
+\end_inset
+
+ grupa,
+\begin_inset Formula $H\subseteq G$
+\end_inset
+
+.
+ za
+\begin_inset Formula $a\in G$
+\end_inset
+
+:
+\begin_inset Formula $aH=\left\{ ah;h\in H\right\} ,Ha=\left\{ ha;h\in H\right\} $
+\end_inset
+
+.
+ Za
+\begin_inset Formula $H$
+\end_inset
+
+ podgrupo pravimo
+\begin_inset Formula $aH$
+\end_inset
+
+ levi odsek
+\begin_inset Formula $H$
+\end_inset
+
+ in
+\begin_inset Formula $Ha$
+\end_inset
+
+ desni.
+ Velja:
+\begin_inset Formula $a\in aH$
+\end_inset
+
+,
+\begin_inset Formula $aH=H\Leftrightarrow a\in H$
+\end_inset
+
+,
+\begin_inset Formula $aH=bH\nabla aH\cap bH=\emptyset$
+\end_inset
+
+,
+\begin_inset Formula $aH=bH\Leftrightarrow a^{-1}b\in H$
+\end_inset
+
+,
+\begin_inset Formula $\left|aH\right|=\left|bH\right|$
+\end_inset
+
+,
+\begin_inset Formula $aH=Ha\Leftrightarrow H=aHa^{-1}$
+\end_inset
+
+,
+\begin_inset Formula $aH\subseteq G\Leftrightarrow a\in H$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+general linear
+\begin_inset Formula $GL_{2}\mathbb{R}=\left\{ A\in M_{2,2}\mathbb{R},\det A\not=0\right\} $
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+special linear
+\begin_inset Formula $SL_{2}\mathbb{R}=\left\{ A\in M_{2,2}\mathbb{R},\det A=1\right\} $
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Lagrange:
+\begin_inset Formula $H$
+\end_inset
+
+ podgrupa končne grupe
+\begin_inset Formula $G\Rightarrow\left|H\right|\text{ deli }\left|G\right|$
+\end_inset
+
+ in število različnih levih/desnih odeskov po
+\begin_inset Formula $H$
+\end_inset
+
+ je
+\begin_inset Formula $\frac{\left|G\right|}{\left|H\right|}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $a\in$
+\end_inset
+
+ končne grupe
+\begin_inset Formula $G\Rightarrow$
+\end_inset
+
+ red
+\begin_inset Formula $a$
+\end_inset
+
+ deli
+\begin_inset Formula $\left|G\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Paragraph
+Podgrupe edinke in faktorske grupe
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $H$
+\end_inset
+
+ podgrupa
+\begin_inset Formula $G$
+\end_inset
+
+ je edinka
+\begin_inset Formula $\Leftrightarrow\forall a\in G:aH=Ha\sim aHa^{-1}=H$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Podgrupa konjugiranka
+\begin_inset Formula $H^{a}\coloneqq aHa^{-1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $H\triangleleft G\sim H$
+\end_inset
+
+ edinka v
+\begin_inset Formula $G$
+\end_inset
+
+
+\begin_inset Formula $\Leftrightarrow\forall a\in G:H^{A}=H$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+V Abelovi grupi je vsaka podgrupa edinka.
+\end_layout
+
+\begin_layout Standard
+Center je podgrupa edinka.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $G/H\coloneqq\left\{ aH:a\in G\right\} $
+\end_inset
+
+ z oper.
+
+\begin_inset Formula $\left(aH\right)*\left(bH\right)=\left(ab\right)H$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Izrek o faktorskih grupah:
+\begin_inset Formula $H\triangleleft G\Rightarrow\left(G/H,*\right)$
+\end_inset
+
+ grupa
+\end_layout
+
+\begin_layout Paragraph
+Kolobarji in polja
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left(R,+,\cdot\right)\text{kolobar}\Rightarrow$
+\end_inset
+
+
+\begin_inset Formula $\left(R,+\right)$
+\end_inset
+
+ abelova grupa,
+\begin_inset Formula $\left(R,\cdot\right)$
+\end_inset
+
+ polgrupa, distributivnost.
+\end_layout
+
+\begin_layout Standard
+Kolobar je komutativen, če je
+\begin_inset Formula $\cdot$
+\end_inset
+
+ komutativna.
+\end_layout
+
+\begin_layout Standard
+Kolobar je z enoto, če obstaja enota za
+\begin_inset Formula $\cdot$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Direktna vsota kolobarjev
+\begin_inset Formula $\left(R\oplus S,+,\cdot\right)$
+\end_inset
+
+ je kolobar.
+
+\begin_inset Formula $R\oplus S=R\times S$
+\end_inset
+
+,
+\begin_inset Formula $+$
+\end_inset
+
+ in
+\begin_inset Formula $\cdot$
+\end_inset
+
+ po komponentah.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $R$
+\end_inset
+
+ in
+\begin_inset Formula $S$
+\end_inset
+
+ komutativna
+\begin_inset Formula $\Rightarrow R\oplus S$
+\end_inset
+
+ komutativen.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $R$
+\end_inset
+
+ in
+\begin_inset Formula $S$
+\end_inset
+
+ z enoto
+\begin_inset Formula $\Rightarrow R\oplus S$
+\end_inset
+
+ z enoto.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $R$
+\end_inset
+
+ kolobar.
+
+\begin_inset Formula $S\subseteq R$
+\end_inset
+
+ je za podedovani operaciji kolobar, če je
+\begin_inset Formula $\left(S,+,\cdot\right)$
+\end_inset
+
+ kolobar.
+ Izrek:
+\begin_inset Formula $S$
+\end_inset
+
+ podkolobar
+\begin_inset Formula $\Leftrightarrow0\in S$
+\end_inset
+
+ in zaprta za
+\begin_inset Formula $-,\cdot$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Center kolobarja:
+\begin_inset Formula $ZR=\left\{ a\in R;\forall x\in R:ax=xa\right\} $
+\end_inset
+
+ je podk.
+\end_layout
+
+\begin_layout Paragraph
+Delitelji niča in celi kolobarji
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left(\mathbb{Z}_{n},+_{n},\cdot_{n}\right)$
+\end_inset
+
+ je vedno kol.
+\end_layout
+
+\begin_layout Standard
+Def.: Če v kolobarju velja
+\begin_inset Formula $ab=0$
+\end_inset
+
+ in
+\begin_inset Formula $a\not=0$
+\end_inset
+
+ in
+\begin_inset Formula $b\not=0$
+\end_inset
+
+, sta
+\begin_inset Formula $a$
+\end_inset
+
+ in
+\begin_inset Formula $b$
+\end_inset
+
+ delitelja niča.
+\end_layout
+
+\begin_layout Standard
+Pravilo krajšanja:
+\begin_inset Formula $\forall a,b,c\in R,a\not=0:ab=ac\Rightarrow b=c$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $R$
+\end_inset
+
+ cel
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+ komutativen z enoto
+\begin_inset Formula $1\not=0$
+\end_inset
+
+ brez deliteljev niča.
+\end_layout
+
+\begin_layout Standard
+Za komutativen z enoto
+\begin_inset Formula $1\not=0$
+\end_inset
+
+ velja: cel
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+ velja prav.
+ krajš.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left(R,+,\cdot\right)$
+\end_inset
+
+ z enoto
+\begin_inset Formula $1\not=0$
+\end_inset
+
+ je polje, če je
+\begin_inset Formula $\left(R\setminus\left\{ 0\right\} ,\cdot\right)$
+\end_inset
+
+ abelova g.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\left(R,+,\cdot\right)$
+\end_inset
+
+ z enoto
+\begin_inset Formula $1\not=0$
+\end_inset
+
+ je obseg, če je
+\begin_inset Formula $\left(R\setminus\left\{ 0\right\} ,\cdot\right)$
+\end_inset
+
+ grupa.
+\end_layout
+
+\begin_layout Standard
+Vsako polje je cel kolobar.
+\end_layout
+
+\begin_layout Standard
+Polje je cel kolobar z multiplik.
+ inverzi za vse neničelne.
+\end_layout
+
+\begin_layout Standard
+Končen cel kolobar
+\begin_inset Formula $\Rightarrow$
+\end_inset
+
+ polje.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\forall n\in\mathbb{N}\setminus\left\{ 1\right\} :\mathbb{Z}_{n}$
+\end_inset
+
+ cel
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+
+\begin_inset Formula $\mathbb{Z}_{n}$
+\end_inset
+
+ polje
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+
+\begin_inset Formula $n$
+\end_inset
+
+ praštevilo
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $S\subseteq$
+\end_inset
+
+ polje
+\begin_inset Formula $R$
+\end_inset
+
+ je podpolje za poded.
+ operaciji, če je
+\begin_inset Formula $S$
+\end_inset
+
+ polje.
+ Zadošča preveriti
+\begin_inset Formula $1\in S$
+\end_inset
+
+, zaprtost za
+\begin_inset Formula $-$
+\end_inset
+
+ in deljenje z nenič.ž
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $n\cdot'a$
+\end_inset
+
+ naj pomeni
+\begin_inset Formula $a+\cdots+a$
+\end_inset
+
+
+\begin_inset Formula $n$
+\end_inset
+
+-krat za
+\begin_inset Formula $n\in\mathbb{N}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Karakteristika kolobarja je najmanjši
+\begin_inset Formula $n\in N\ni:\forall a\in R:n\cdot'a=0$
+\end_inset
+
+.
+ Če ne obstaja, pravimo char
+\begin_inset Formula $R=0$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Izrek: Če je red1
+\begin_inset Formula $=n\Rightarrow$
+\end_inset
+
+ char
+\begin_inset Formula $R=n$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Izrek: Za cel kolobar
+\begin_inset Formula $R$
+\end_inset
+
+ je char
+\begin_inset Formula $R=0$
+\end_inset
+
+ ali char
+\begin_inset Formula $R=$
+\end_inset
+
+ praštevilo
+\end_layout
+
+\begin_layout Paragraph
+Ideali
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $S$
+\end_inset
+
+ podkolobar
+\begin_inset Formula $R$
+\end_inset
+
+ je ideal
+\begin_inset Formula $R\Leftrightarrow\forall r\in R,s\in S:rs,sr\in S$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Primer: večkratniki
+\begin_inset Formula $n$
+\end_inset
+
+ so za fiksen
+\begin_inset Formula $n$
+\end_inset
+
+ ideal v
+\begin_inset Formula $\mathbb{Z}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $I\subseteq R$
+\end_inset
+
+ je ideal
+\begin_inset Formula $\Leftrightarrow0\in I$
+\end_inset
+
+, zaprt za
+\begin_inset Formula $-$
+\end_inset
+
+, zaprt za zunanje množ.
+\end_layout
+
+\begin_layout Standard
+Operaciji nad ideali:
+\begin_inset Formula $I\overset{+}{\cdot}J=\left\{ i\overset{+}{\cdot}j;\forall i\in I,j\in J\right\} $
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Za ideala
+\begin_inset Formula $I,J$
+\end_inset
+
+ v
+\begin_inset Formula $R$
+\end_inset
+
+ sta
+\begin_inset Formula $I+J$
+\end_inset
+
+ in
+\begin_inset Formula $I\cdot J$
+\end_inset
+
+ zopet ideala v
+\begin_inset Formula $R$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+V aditivne odseke
+\begin_inset Formula $R/I=\left\{ a+I;\forall a\in R\right\} $
+\end_inset
+
+ vpeljemo operaciji
+\begin_inset Formula $\left(a+I\right)\overset{+}{\cdot}\left(b+I\right)=\left(a\overset{+}{\cdot}b\right)I$
+\end_inset
+
+.
+ Če je
+\begin_inset Formula $I$
+\end_inset
+
+ ideal v
+\begin_inset Formula $R$
+\end_inset
+
+, je
+\begin_inset Formula $R/I$
+\end_inset
+
+ za operaciji kolobar.
+\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
diff --git a/šola/ds2/teor.lyx b/šola/ds2/teor.lyx
new file mode 100644
index 0000000..c0fe332
--- /dev/null
+++ b/šola/ds2/teor.lyx
@@ -0,0 +1,7562 @@
+#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{hyperref}
+\usepackage{siunitx}
+\usepackage{pgfplots}
+\usepackage{listings}
+\usepackage{multicol}
+\sisetup{output-decimal-marker = {,}, quotient-mode=fraction, output-exponent-marker=\ensuremath{\mathrm{3}}}
+\usepackage{amsmath}
+\usepackage{tikz}
+\newcommand{\udensdash}[1]{%
+ \tikz[baseline=(todotted.base)]{
+ \node[inner sep=1pt,outer sep=0pt] (todotted) {#1};
+ \draw[densely dashed] (todotted.south west) -- (todotted.south east);
+ }%
+}%
+\DeclareMathOperator{\Lin}{Lin}
+\DeclareMathOperator{\rang}{rang}
+\DeclareMathOperator{\sled}{sled}
+\DeclareMathOperator{\Aut}{Aut}
+\DeclareMathOperator{\red}{red}
+\DeclareMathOperator{\karakteristika}{char}
+\usepackage{algorithm,algpseudocode}
+\providecommand{\corollaryname}{Posledica}
+\end_preamble
+\use_default_options true
+\begin_modules
+enumitem
+theorems-ams
+\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 default
+\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 2cm
+\topmargin 2cm
+\rightmargin 2cm
+\bottommargin 2cm
+\headheight 2cm
+\headsep 2cm
+\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 Title
+Odgovori na vprašanja za teoretični del izpita DS2 IŠRM 2023/24
+\end_layout
+
+\begin_layout Author
+
+\noun on
+Anton Luka Šijanec
+\end_layout
+
+\begin_layout Date
+\begin_inset ERT
+status open
+
+\begin_layout Plain Layout
+
+
+\backslash
+today
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Abstract
+Vprašanja je zbral profesor Sandi Klavžar.
+ Odgovore sem sestavil po svojih zapiskih z njegovih predavanj in drugih
+ virih.
+\end_layout
+
+\begin_layout Standard
+\begin_inset CommandInset toc
+LatexCommand tableofcontents
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Section
+Slog
+\end_layout
+
+\begin_layout Itemize
+Z
+\begin_inset Formula $M_{m,n}\mathbb{F}$
+\end_inset
+
+ označim množico matrik z
+\begin_inset Formula $m$
+\end_inset
+
+ vrsticami in
+\begin_inset Formula $n$
+\end_inset
+
+ stolpci nad poljem
+\begin_inset Formula $\mathbb{F}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Itemize
+Znak za množenje ali dvojiški operator v grupi izpuščam.
+ V bigrupoidih izpuščen operator pomeni množenje (drugo operacijo).
+\end_layout
+
+\begin_layout Section
+Vprašanja in odgovori
+\end_layout
+
+\begin_layout Subsection
+Kaj je stopnja vozlišča grafa in kaj pravi lema o rokovanju? Kako dokažemo
+ to lemo?
+\end_layout
+
+\begin_layout Standard
+Naj bo
+\begin_inset Formula $G$
+\end_inset
+
+ graf.
+\end_layout
+
+\begin_layout Definition*
+Stopnja vozlišča grafa
+\begin_inset Formula $\deg v$
+\end_inset
+
+ za
+\begin_inset Formula $v\in VG$
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Ko eniški operator zahteva en operand, izpustim oklepaje.
+ Primer:
+\begin_inset Formula $\sin x$
+\end_inset
+
+,
+\begin_inset Formula $VG$
+\end_inset
+
+,
+\begin_inset Formula $\chi G$
+\end_inset
+
+,
+\begin_inset Formula $M_{2,2}\mathbb{R}$
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+ predstavlja število povezav, ki imajo to vozlišče kot krajišče.
+
+\begin_inset Formula $\deg v=\left|\left\{ e\in EG;v\in e\right\} \right|$
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Povezava v grafu je množica natanko dveh vozlišč, toda oklepaje in vejico
+ izpuščam.
+ Za
+\begin_inset Formula $u,v\in VG$
+\end_inset
+
+ pišem
+\begin_inset Formula $uv\in EG$
+\end_inset
+
+.
+ Na
+\begin_inset Formula $e\in EG$
+\end_inset
+
+ je torej veljavno gledati kot na množico, zato je
+\begin_inset Formula $v\in e$
+\end_inset
+
+ smiseln izraz.
+\end_layout
+
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Zapis množic:
+\begin_inset Formula $\left\{ e\in A;Pe\right\} $
+\end_inset
+
+ pomeni vse take elemente
+\begin_inset Formula $A$
+\end_inset
+
+, za katere velja predikat
+\begin_inset Formula $P$
+\end_inset
+
+.
+ Ta predikat je običajno izraz.
+\end_layout
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Incidenčna matrika
+\begin_inset Formula $BG$
+\end_inset
+
+ za
+\begin_inset Formula $VG=\left\{ v_{1},\dots,v_{n}\right\} $
+\end_inset
+
+,
+\begin_inset Formula $EG=\left\{ e_{1},\dots,e_{n}\right\} $
+\end_inset
+
+ je široka
+\begin_inset Formula $m$
+\end_inset
+
+ in visoka
+\begin_inset Formula $n$
+\end_inset
+
+ in velja
+\begin_inset Formula $BG_{ij}=\begin{cases}
+1 & ;v_{i}\in e_{i}\\
+0 & ;\text{sicer}
+\end{cases}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Lemma*
+Lema o rokovanju pravi, da je dvakratnik števila povezav enak vsoti vseh
+ stopenj vozlišč v grafu
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Ko je omenjen graf, je običajno mišljen neusmerjen končen graf.
+\end_layout
+
+\end_inset
+
+, torej
+\begin_inset Formula
+\[
+\sum_{v\in VG}\deg v=2\left|EG\right|.
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Remark*
+Posledica leme o rokovanju je, da je v vsakem grafu sodo vozlišč lihe stopnje,
+ saj je vsota soda.
+\end_layout
+
+\begin_layout Proof
+Če po vozliščih preštevamo povezave, ki se stikajo vozlišča, bi vsako povezavo
+ šteli dvakrat; vsakič za eno njeno krajišče.
+ ZDB V vsakem stolpcu incidenčne matrike sta natanko dve enici.
+ Torej je enic
+\begin_inset Formula $2\left|EG\right|$
+\end_inset
+
+.
+ V vsaki vrstici incidenčne matrike je toliko enic, kolikor je stopnja
+\begin_inset Formula $i-$
+\end_inset
+
+tega vozlišča, torej je enic
+\begin_inset Formula $\sum_{v\in VG}\deg v$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsection
+Pojasnite sprehod, sklenjen sprehod, pot v grafu, cikel v grafu.
+ Pokažite, da vsak graf, ki vsebuje sklenjen sprehod lihe dolžine, vsebuje
+ tudi cikel lihe dolžine.
+\end_layout
+
+\begin_layout Standard
+Naj bo
+\begin_inset Formula $G=\left(VG,EG\right)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Definition*
+Sprehod v
+\begin_inset Formula $G$
+\end_inset
+
+ je zaporedje vozlišč
+\begin_inset Formula $v_{0},\dots,v_{k}$
+\end_inset
+
+,
+\begin_inset Formula $k\geq0$
+\end_inset
+
+, tako da je
+\begin_inset Formula $\forall i\in\left\{ 1..k\right\} :v_{i}v_{i+1}\in EG$
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+S
+\begin_inset Formula $\left\{ k..n\right\} $
+\end_inset
+
+ označujem množico celih števil od vključno
+\begin_inset Formula $k$
+\end_inset
+
+ do vključno
+\begin_inset Formula $n$
+\end_inset
+
+, kot to naredi
+\family typewriter
+bash
+\end_layout
+
+\end_inset
+
+.
+ Nekateri bi
+\begin_inset Formula $\left\{ 1..n\right\} $
+\end_inset
+
+ označili z
+\begin_inset Formula $\left[n\right]$
+\end_inset
+
+..
+ Dolžina sprehoda je število prehojenih povezav.
+ Sprehod je
+\series bold
+sklenjen
+\series default
+, če
+\begin_inset Formula $v_{0}=v_{k}$
+\end_inset
+
+.
+ Sprehod je
+\series bold
+enostaven
+\series default
+, če so vsa vozlišča medsebojno različna, z izjemo
+\begin_inset Formula $v_{0}$
+\end_inset
+
+ sme biti
+\begin_inset Formula $v_{k}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Claim*
+Če v grafu
+\begin_inset Formula $\exists$
+\end_inset
+
+ sprehod med dvema vozliščema, med njima obstaja tudi enostaven sprehod.
+\end_layout
+
+\begin_layout Proof
+Naj bo
+\begin_inset Formula $Q$
+\end_inset
+
+ sprehod med
+\begin_inset Formula $u$
+\end_inset
+
+ in
+\begin_inset Formula $v$
+\end_inset
+
+.
+ Če je enostaven, je najden, sicer se ponovita vsaj dve vozlišči in je
+\begin_inset Formula $Q$
+\end_inset
+
+ oblike
+\begin_inset Formula $u,\dots,x,\dots,x,\dots,v$
+\end_inset
+
+.
+ Sprehodu priredimo
+\begin_inset Formula $Q'$
+\end_inset
+
+, ki odstrani pot od prvega do zadnjega podvojenega vozlišča
+\begin_inset Formula $x$
+\end_inset
+
+, torej je
+\begin_inset Formula $Q'$
+\end_inset
+
+ oblike
+\begin_inset Formula $u,\dots,x,\dots,v$
+\end_inset
+
+ (pravzaprav smo odstranili cikel iz poti).
+ Če je
+\begin_inset Formula $Q'$
+\end_inset
+
+ enostaven, je iskani, sicer postopek ponovimo in v končno korakih se postopek
+ ustavi, saj na vsakem koraku za vsaj 2 zmanjšamo dolžino sicer končno dolgega
+ sprehoda.
+\end_layout
+
+\begin_layout Definition*
+Pot v grafu je podgraf, ki je enostaven sprehod med dvema vozliščema in
+ je graf Pot (
+\begin_inset Formula $P_{n}$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Remark*
+Ko govorimo o različnosti/enakosti poti, mislimo različnost/enakost poti
+ kot podgraf.
+ Poti sta torej enaki natanko tedaj, ko sta zaporedji (ne množici) vozlišč
+ poti enaki.
+\end_layout
+
+\begin_layout Definition*
+Cikel v grafu je podgraf, ki je enostaven sklenjen sprehod dolžine vsaj
+ 3.
+\end_layout
+
+\begin_layout Claim*
+Če med dvema vozliščema v grafu
+\begin_inset Formula $\exists$
+\end_inset
+
+ dve različni poti, potem graf premore cikel.
+\end_layout
+
+\begin_layout Proof
+Naj bosta
+\begin_inset Formula $P$
+\end_inset
+
+ in
+\begin_inset Formula $P'$
+\end_inset
+
+ dve različni poti od
+\begin_inset Formula $u$
+\end_inset
+
+ do
+\begin_inset Formula $v$
+\end_inset
+
+.
+ Naj bo
+\begin_inset Formula $x$
+\end_inset
+
+ zadnje (če gledamo usmerjeno
+\begin_inset Formula $u,v-$
+\end_inset
+
+pot) vozlišče, ki je skupno
+\begin_inset Formula $P$
+\end_inset
+
+ in
+\begin_inset Formula $P'$
+\end_inset
+
+.
+
+\begin_inset Formula $x$
+\end_inset
+
+ je lahko
+\begin_inset Formula $u$
+\end_inset
+
+.
+ Naj bo
+\begin_inset Formula $g$
+\end_inset
+
+ prvo naslednje vozlišče za
+\begin_inset Formula $x$
+\end_inset
+
+, ki je na
+\begin_inset Formula $P$
+\end_inset
+
+ in
+\begin_inset Formula $P'$
+\end_inset
+
+.
+ Unija podpoti
+\begin_inset Formula $P$
+\end_inset
+
+ od
+\begin_inset Formula $x$
+\end_inset
+
+ do
+\begin_inset Formula $y$
+\end_inset
+
+ in podpoti
+\begin_inset Formula $P'$
+\end_inset
+
+ od
+\begin_inset Formula $x$
+\end_inset
+
+ do
+\begin_inset Formula $y$
+\end_inset
+
+ določa iskani cikel v grafu.
+\end_layout
+
+\begin_layout Claim*
+Če graf premore sklenjen sprehod lihe dolžine, potem premore cikel lihe
+ dolžine.
+\end_layout
+
+\begin_layout Proof
+Indukcija po dolžini sprehoda.
+ Naj bo
+\begin_inset Formula $m$
+\end_inset
+
+ dolžina sprehoda.
+\end_layout
+
+\begin_layout Proof
+Baza:
+\begin_inset Formula $m=3$
+\end_inset
+
+, najmanjši sklenjen lihi sprehod je cikel dolžine 3,
+\begin_inset Formula $m=4$
+\end_inset
+
+, drugi najmanjši sklenjen lihi sprehod je cikel dolžine 4.
+\end_layout
+
+\begin_layout Proof
+Korak: Naj bo
+\begin_inset Formula $Q$
+\end_inset
+
+ poljuben sklenjen sprehod dolžine
+\begin_inset Formula $m\geq5$
+\end_inset
+
+.
+ Če je
+\begin_inset Formula $Q$
+\end_inset
+
+ enostaven, je cikel po definiciji, sicer se vsaj eno vozlišče na sprehodu
+ vsaj ponovi:
+\begin_inset Formula $u,x_{1},\dots,x_{i-1},x_{i},x_{i+1},\dots,x_{j-1},x_{j},x_{j+1},\dots,v$
+\end_inset
+
+ in velja
+\begin_inset Formula $x_{i}=x_{j}$
+\end_inset
+
+.
+ Poglejmo sprehoda
+\begin_inset Formula $Q'=x_{i},\dots,x_{j}=x_{i}$
+\end_inset
+
+ in
+\begin_inset Formula $Q''=u,x_{1},\dots,x_{i},x_{j+1},\dots,x_{m}=u$
+\end_inset
+
+.
+
+\begin_inset Formula $Q'$
+\end_inset
+
+ in
+\begin_inset Formula $Q''$
+\end_inset
+
+ sta sklenjena sprehoda z dolžinama
+\begin_inset Formula $m'$
+\end_inset
+
+ in
+\begin_inset Formula $m''$
+\end_inset
+
+ in velja
+\begin_inset Formula $m=m'+m''$
+\end_inset
+
+.
+ Ker je
+\begin_inset Formula $m$
+\end_inset
+
+ lih, mora biti lih natanko en izmed
+\begin_inset Formula $m'$
+\end_inset
+
+ in
+\begin_inset Formula $m''$
+\end_inset
+
+.
+ BSŠ
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Brez Škode za Splošnost trdimo, da
+\end_layout
+
+\end_inset
+
+
+\begin_inset Formula $m'$
+\end_inset
+
+ lih in
+\begin_inset Formula $m'<m$
+\end_inset
+
+, zato po I.
+ P.
+
+\begin_inset Formula $m'$
+\end_inset
+
+ vsebuje lih cikel.
+\end_layout
+
+\begin_layout Subsection
+Kaj so dvodelni grafi? Kako jih karakteriziramo? Kako dokažemo to karakterizacij
+o?
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $G$
+\end_inset
+
+ dvodelen
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Pomožni glagol biti med osebkom in povedkovnikom izpuščam.
+
+\begin_inset Quotes gld
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ dvodelen
+\begin_inset Quotes grd
+\end_inset
+
+ namesto
+\begin_inset Quotes gld
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ je dvodelen
+\begin_inset Quotes grd
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+
+\begin_inset Formula $\Leftrightarrow\exists A,B\subseteq VG\ni:A\cup B=VG,A\cap B=\emptyset\ni:\forall uv\in EG:u\in A,v\in B\vee v\in A,u\in B$
+\end_inset
+
+.
+ ZDB
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Z Drugimi Besedami:
+\end_layout
+
+\end_inset
+
+ obstaja razdelitev vozlišč na dve množici, da induciran podgraf posamezne
+ množice ne vsebuje povezav.
+ S
+\begin_inset Formula $K_{m,n}$
+\end_inset
+
+ označimo poln dvodelni graf
+\begin_inset Formula $\left|A\right|=m$
+\end_inset
+
+,
+\begin_inset Formula $\left|B\right|=n$
+\end_inset
+
+.
+ Paru
+\begin_inset Formula $\left(A,B\right)$
+\end_inset
+
+ pravimo dvodelna razdelitev.
+\end_layout
+
+\begin_layout Theorem*
+\begin_inset Formula $G$
+\end_inset
+
+ dvodelen
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ ne vsebuje lihih ciklov.
+\end_layout
+
+\begin_layout Proof
+\begin_inset Formula $G$
+\end_inset
+
+ dvodelen
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+ vsaka komponenta
+\begin_inset Formula $G$
+\end_inset
+
+ dvodelna, zato BSŠ
+\begin_inset Formula $G$
+\end_inset
+
+ povezan.
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(\Rightarrow\right)$
+\end_inset
+
+ Očitno: Če
+\begin_inset Formula $G$
+\end_inset
+
+ vsebuje lih cikel, zagotovo ni dvodelen, saj ne moremo razdeliti niti množice
+ vozlišč cikla.
+ S skico dokažemo, da sodi cikli so dvodelni, lihi pa niso (narišemo cikel
+ kot pot v obliki skeletne formule nenasičenega acikličnega alkana in povežemo
+ prvo in zadnje vozlišče).
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(\Leftarrow\right)$
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ je po predpostavki brez lihih ciklov ****.
+ Izberimo poljubno
+\begin_inset Formula $x_{0}\in VG$
+\end_inset
+
+.
+ Naj bo
+\begin_inset Formula $A=\left\{ u\in VG;d_{G}\left(u,x_{0}\right)\text{ sod}\right\} ,B=\left\{ u\in VG;d_{G}\left(u,x_{0}\right)\text{ lih}\right\} $
+\end_inset
+
+.
+
+\begin_inset Formula $x_{0}$
+\end_inset
+
+ je torej v
+\begin_inset Formula $A$
+\end_inset
+
+, saj je
+\begin_inset Formula $d_{G}\left(x_{0},x_{0}\right)=0$
+\end_inset
+
+.
+ Trdimo, da je
+\begin_inset Formula $\left(A,B\right)$
+\end_inset
+
+ dvodelna razdelitev
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Razdelitev je, ker je
+\begin_inset Formula $A\cup B=\emptyset$
+\end_inset
+
+ in
+\begin_inset Formula $A\cup B=VG$
+\end_inset
+
+.
+ Za dvodelnost pa mora veljati
+\begin_inset Formula $\forall X\in\left\{ A,B\right\} :\forall u,v\in X:uv\not\in EG$
+\end_inset
+
+.
+ Preverimo za splošen fiksen
+\begin_inset Formula $X\in\left\{ A,B\right\} $
+\end_inset
+
+: Naj bosta
+\begin_inset Formula $u,v\in X$
+\end_inset
+
+, BSŠ
+\begin_inset Formula $d_{G}\left(x_{0},u\right)>d_{G}\left(x_{0},v\right)$
+\end_inset
+
+ *.
+ Ločimo dva primera:
+\end_layout
+
+\begin_deeper
+\begin_layout Description
+\begin_inset Formula $d_{G}\left(x_{0},u\right)\not=d_{G}\left(x_{0},v\right):$
+\end_inset
+
+ Vsled iste parnosti velja
+\begin_inset Formula $\left|d_{G}\left(x_{0},u\right)-d_{G}\left(x_{0},v\right)\right|\geq2$
+\end_inset
+
+ ***.
+ PDDRAA
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Pa Denimo Da sledeča trditev ne drži (Reductio Ad Absurdum)
+\end_layout
+
+\end_inset
+
+
+\begin_inset Formula $uv\in EG$
+\end_inset
+
+, tedaj se
+\begin_inset Formula $d_{G}\left(x_{0},u\right)$
+\end_inset
+
+ in
+\begin_inset Formula $d_{G}\left(x_{0},v\right)$
+\end_inset
+
+ razlikujeta za največ 1 in velja
+\begin_inset Formula $d_{G}\left(x_{0},u\right)\leq d_{G}\left(x_{0},v\right)+1$
+\end_inset
+
+ **.
+ Iz * in ** sledi
+\begin_inset Formula $d_{G}\left(x_{0},u\right)-d_{G}\left(x_{0},v\right)=1$
+\end_inset
+
+, kar je v
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+ s trditvijo ***.
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $d_{G}\left(x_{0},u\right)=d_{G}\left(x_{0},v\right):$
+\end_inset
+
+ Naj bo
+\begin_inset Formula $P_{x}$
+\end_inset
+
+ najkrajša
+\begin_inset Formula $x_{0},x-$
+\end_inset
+
+pot.
+ PDDRAA
+\begin_inset Formula $uv\in EG$
+\end_inset
+
+, tedaj
+\begin_inset Formula $P_{u}=\left\{ ...P_{v},v\right\} $
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Prefiksni razširitveni operator
+\begin_inset Formula $...$
+\end_inset
+
+ razširi množico oziroma v tem primeru zaporedje v seznam elementov.
+ S tem lahko množico uporabimo kot seznam.
+ Povzemam operator
+\family typewriter
+...
+
+\family default
+ iz javascripta.
+\end_layout
+
+\end_inset
+
+, torej
+\begin_inset Formula $\left|P_{u}\right|=1+\left|P_{v}\right|$
+\end_inset
+
+.
+ Cikel, ki ga tvorijo
+\begin_inset Formula $P_{u}$
+\end_inset
+
+,
+\begin_inset Formula $P_{v}$
+\end_inset
+
+ in povezava
+\begin_inset Formula $uv$
+\end_inset
+
+, je torej dolžine
+\begin_inset Formula $2\left|P_{v}\right|+1$
+\end_inset
+
+, kar je liho število, kar je v
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+ s trditvijo ****.
+\end_layout
+
+\end_deeper
+\begin_layout Subsection
+Kaj je homomorfizem grafov, izomorfizem grafov in avtomorfizem grafa? Kaj
+ je to
+\begin_inset Formula $\Aut\left(G\right)$
+\end_inset
+
+? Kakšno algebrsko strukturo ima?
+\end_layout
+
+\begin_layout Standard
+Naj bosta
+\begin_inset Formula $G$
+\end_inset
+
+ in
+\begin_inset Formula $H$
+\end_inset
+
+ grafa.
+\end_layout
+
+\begin_layout Definition*
+Preslikava
+\begin_inset Formula $f:VG\to VH$
+\end_inset
+
+ je hm
+\begin_inset Formula $\varphi$
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+homomorfizem
+\end_layout
+
+\end_inset
+
+ grafov
+\begin_inset Formula $G$
+\end_inset
+
+ in
+\begin_inset Formula $H\Leftrightarrow\forall u,v\in VG:uv\in EG\Rightarrow fufv\in EH$
+\end_inset
+
+, ZDB če slika povezave v povezave.
+\end_layout
+
+\begin_layout Remark*
+Če je
+\begin_inset Formula $f$
+\end_inset
+
+ hm
+\begin_inset Formula $\text{\ensuremath{\varphi}},$
+\end_inset
+
+porodi preslikavo
+\begin_inset Formula $f':EG\to EH$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $f:VK_{n,m}\to VK_{2}$
+\end_inset
+
+ s predpisom
+\begin_inset Formula $fx=\begin{cases}
+u & ;x\in A\\
+v & ;x\in B
+\end{cases}$
+\end_inset
+
+ je hm
+\begin_inset Formula $\varphi$
+\end_inset
+
+.
+
+\begin_inset Formula $K_{2}$
+\end_inset
+
+ je homomorfna slika vsakega dvodelnega grafa.
+\end_layout
+
+\begin_layout Definition*
+Če je hm
+\begin_inset Formula $\varphi$
+\end_inset
+
+ surjektiven po povezavah in vozliščih, je epimorfizem.
+ Če je injektiven na vozliščih (in posledično na povezavah), je monomorfizem
+ ali vložitev.
+ Vložitev je izometrična, če
+\begin_inset Formula $\forall u,v\in VG:d_{G}\left(u,v\right)=d_{H}\left(fu,fv\right)$
+\end_inset
+
+ ZDB ohranja razdalje.
+\end_layout
+
+\begin_layout Claim*
+Če sta
+\begin_inset Formula $f:VG\to VH$
+\end_inset
+
+ in
+\begin_inset Formula $g:VH\to VK$
+\end_inset
+
+ hm
+\begin_inset Formula $\varphi$
+\end_inset
+
+, je
+\begin_inset Formula $g\circ f:VG\to VK$
+\end_inset
+
+ spet hm
+\begin_inset Formula $\varphi$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Definition*
+Če je
+\begin_inset Formula $f:VG\to VH$
+\end_inset
+
+ bijekcija, hm
+\begin_inset Formula $\varphi$
+\end_inset
+
+ in
+\begin_inset Formula $f^{-1}$
+\end_inset
+
+ hm
+\begin_inset Formula $\varphi$
+\end_inset
+
+ (ZDB slika nepovezave v nepovezave), je
+\begin_inset Formula $f$
+\end_inset
+
+ im
+\begin_inset Formula $\varphi$
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+izomorfizem
+\end_layout
+
+\end_inset
+
+ grafov
+\begin_inset Formula $G$
+\end_inset
+
+ in
+\begin_inset Formula $H$
+\end_inset
+
+.
+ ZDB
+\begin_inset Formula $f:VG\to VH$
+\end_inset
+
+ im
+\begin_inset Formula $\varphi$
+\end_inset
+
+
+\begin_inset Formula $\Leftrightarrow f$
+\end_inset
+
+ bijekcija
+\begin_inset Formula $\wedge\forall u,v\in VG:uv\in EG\Leftrightarrow fufv\in EH$
+\end_inset
+
+.
+ Če
+\begin_inset Formula $\text{\ensuremath{\exists}}$
+\end_inset
+
+ im
+\begin_inset Formula $\varphi$
+\end_inset
+
+ grafov
+\begin_inset Formula $G$
+\end_inset
+
+ in
+\begin_inset Formula $H$
+\end_inset
+
+, pravimo, da sta
+\begin_inset Formula $G$
+\end_inset
+
+ in
+\begin_inset Formula $H$
+\end_inset
+
+ izomorfna in pišemo
+\begin_inset Formula $G\cong H$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $\cong$
+\end_inset
+
+ je na
+\begin_inset Formula $\mathcal{G}$
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+množica vseh grafov
+\end_layout
+
+\end_inset
+
+ ekvivalenčna (refleksivna, simetrična, tranzitivna).
+\end_layout
+
+\begin_layout Definition*
+im
+\begin_inset Formula $\varphi$
+\end_inset
+
+
+\begin_inset Formula $G\to G$
+\end_inset
+
+ je am
+\begin_inset Formula $\varphi$
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+avtomorfizem
+\end_layout
+
+\end_inset
+
+.
+ Vse am
+\begin_inset Formula $\varphi$
+\end_inset
+
+ grafa
+\begin_inset Formula $G$
+\end_inset
+
+ združimo v množico in jo opremimo z operacijo komponiranja.
+ Dobimo
+\begin_inset Quotes gld
+\end_inset
+
+grupo avtomorfizmov grafa
+\begin_inset Formula $G$
+\end_inset
+
+
+\begin_inset Quotes grd
+\end_inset
+
+, ki jo označimo z
+\begin_inset Formula $\Aut G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\Aut C_{4}=\left(\left\{ id,\left(2,4\right),\left(12\right)\left(34\right),\left(1234\right),\left(13\right),\left(13\right)\left(24\right),\left(1423\right),\left(4321\right)\right\} ,\circ\right)$
+\end_inset
+
+,
+\begin_inset Formula $\Aut K_{n}=\left(S_{n},\circ\right)$
+\end_inset
+
+ za
+\begin_inset Formula $S_{n}$
+\end_inset
+
+ množica vseh permutacij
+\begin_inset Formula $n$
+\end_inset
+
+ elementov,
+\begin_inset Formula $\Aut P_{n}=\left(\left\{ id,f\left(i\right)=n-i-1\right\} ,\circ\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Fact*
+Za vsako končno grupo
+\begin_inset Formula $X$
+\end_inset
+
+
+\begin_inset Formula $\exists$
+\end_inset
+
+ graf
+\begin_inset Formula $G\ni:\Aut G=X$
+\end_inset
+
+.
+ Algebra
+\begin_inset Formula $\subseteq$
+\end_inset
+
+ Diskretne strukture.
+ Dokaz na magisteriju.
+\end_layout
+
+\begin_layout Subsection
+Kaj pomeni, da je graf
+\begin_inset Formula $H$
+\end_inset
+
+ minor grafa
+\begin_inset Formula $G$
+\end_inset
+
+? Kdaj sta dva grafa homeomorfna? Pojasni operacijo kartezičnega produkta
+ grafov.
+\end_layout
+
+\begin_layout Definition*
+
+\series bold
+Odstranjevanje vozlišč
+\series default
+: za neko
+\begin_inset Formula $S\subseteq VG$
+\end_inset
+
+ je
+\begin_inset Formula $G-S$
+\end_inset
+
+ graf, ki ga dobimo, ko iz
+\begin_inset Formula $G$
+\end_inset
+
+ odstranimo vozlišča in vozliščem pripadajoče povezave iz
+\begin_inset Formula $S$
+\end_inset
+
+.
+ Za
+\begin_inset Formula $S=\left\{ u\right\} $
+\end_inset
+
+ pišemo tudi
+\begin_inset Formula $G-u$
+\end_inset
+
+.
+
+\series bold
+Odstranjevanje povezav
+\series default
+: za neko
+\begin_inset Formula $F\subseteq EG$
+\end_inset
+
+ je
+\begin_inset Formula $G-F$
+\end_inset
+
+ graf, ki ga dobimo, ko iz
+\begin_inset Formula $G$
+\end_inset
+
+ odstranimo povezave iz
+\begin_inset Formula $F$
+\end_inset
+
+.
+ Za
+\begin_inset Formula $S=\left\{ e\right\} $
+\end_inset
+
+ pišemo tudi
+\begin_inset Formula $G-e$
+\end_inset
+
+.
+
+\series bold
+Skrčitev povezave
+\series default
+: za
+\begin_inset Formula $e=\left\{ u,v\right\} \in EG$
+\end_inset
+
+ je
+\begin_inset Formula $G/e$
+\end_inset
+
+ graf, ki ga dobimo tako, da identificiramo
+\begin_inset Formula $u$
+\end_inset
+
+ in
+\begin_inset Formula $v$
+\end_inset
+
+ in odstranimo morebitne vzporedne povezave, s čimer odstranimo tudi zanko
+
+\begin_inset Formula $\left\{ u,u=v\right\} $
+\end_inset
+
+.
+
+\begin_inset Formula $G/e_{1}/e_{2}/\dots/e_{n}$
+\end_inset
+
+ označimo z
+\begin_inset Formula $G/\left\{ e_{1},e_{2},\dots,e_{n}\right\} $
+\end_inset
+
+ .
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $H$
+\end_inset
+
+ minor
+\begin_inset Formula $G\Leftrightarrow$
+\end_inset
+
+
+\begin_inset Formula $H$
+\end_inset
+
+ dobimo iz
+\begin_inset Formula $G$
+\end_inset
+
+ z nekim zaporedjem operacij, kjer so dovoljene operacije odstranjevanje
+ vozlišča, odstranjevanje povezave in skrčitev povezave.
+ Ekvivalentno je
+\begin_inset Formula $H$
+\end_inset
+
+ minor
+\begin_inset Formula $G$
+\end_inset
+
+, če ga lahko dobimo iz nekega podgrafa
+\begin_inset Formula $G$
+\end_inset
+
+, ki mu skrčimo poljubno povezav.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Subdivizija povezav:
+\begin_inset Formula $G\to G^{+}e$
+\end_inset
+
+ za
+\begin_inset Formula $e\in EG$
+\end_inset
+
+:
+\begin_inset Formula $VG^{+}e=VG\cup\left\{ x_{e}\right\} $
+\end_inset
+
+,
+\begin_inset Formula $EG^{+}e=EG\setminus e\cup\left\{ x_{e}u,x_{e}v\right\} $
+\end_inset
+
+.
+ Graf
+\begin_inset Formula $H$
+\end_inset
+
+ je subdivizija
+\begin_inset Formula $G\Leftrightarrow H$
+\end_inset
+
+ dobimo iz
+\begin_inset Formula $G$
+\end_inset
+
+ z zaporedjem subdivizij povezav
+\begin_inset Formula $G$
+\end_inset
+
+ ZDB povezave v
+\begin_inset Formula $G$
+\end_inset
+
+ zamenjamo s poljubno dolčimi potmi.
+ Relacija je refleksivna (
+\begin_inset Formula $G$
+\end_inset
+
+ subdivizija
+\begin_inset Formula $G$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Glajenje vozlišča
+\begin_inset Formula $u$
+\end_inset
+
+ stopnje
+\begin_inset Formula $2$
+\end_inset
+
+: (obratna operacija od subdivizije)
+\begin_inset Formula $G^{-}u=\left(VG\setminus u,\left(EG\setminus\left\{ e,f\right\} \right)\cup\left\{ \left\{ v,w\right\} \right\} \right)$
+\end_inset
+
+, kjer sta
+\begin_inset Formula $e$
+\end_inset
+
+ in
+\begin_inset Formula $f$
+\end_inset
+
+ povezavi, ki vsebujeta
+\begin_inset Formula $u$
+\end_inset
+
+,
+\begin_inset Formula $v$
+\end_inset
+
+ in
+\begin_inset Formula $w$
+\end_inset
+
+ pa njuni drugi krajišči (tisti krajišči, ki nista
+\begin_inset Formula $u$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Grafa sta homeomorfna, če sta izomorfna po gladitvi vseh vozlišč stopnje
+ 2.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Naj bosta
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $H$
+\end_inset
+
+ grafa.
+ Kartezični produkt grafov
+\begin_inset Formula $G$
+\end_inset
+
+ in
+\begin_inset Formula $H$
+\end_inset
+
+ označimo z
+\begin_inset Formula $G\square H$
+\end_inset
+
+:
+\begin_inset Formula $V\left(G\square H\right)=VG\times VH,E\left(G\square H\right)=\left\{ \left(g,h\right)\left(g',h'\right);g=g'\wedge hh'\in EH\vee h=h'\wedge gg'\in EG\right\} $
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Remark*
+\begin_inset Formula $\left(\mathcal{G},\square\right)$
+\end_inset
+
+ je monoid, kajti
+\begin_inset Formula $K_{1}$
+\end_inset
+
+ je enota, operacija je komutativna in notranja.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $K_{2}\square K_{2}\cong C_{4}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+Kaj so to prerezna vozlišča in prerezne povezave grafa? Kdaj je graf
+\begin_inset Formula $k-$
+\end_inset
+
+povezan in kaj je to povezanost grafa?
+\end_layout
+
+\begin_layout Standard
+Naj bo
+\begin_inset Formula $G$
+\end_inset
+
+ graf z
+\begin_inset Formula $m$
+\end_inset
+
+ vozlišči.
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $u,v\in VG$
+\end_inset
+
+ sta v isti povezani komponenti, če v
+\begin_inset Formula $G$
+\end_inset
+
+ obstaja sprehod med njima.
+ Število komponent
+\begin_inset Formula $G$
+\end_inset
+
+ označimo z
+\begin_inset Formula $\Omega G$
+\end_inset
+
+.
+
+\begin_inset Formula $G$
+\end_inset
+
+ povezan
+\begin_inset Formula $\Leftrightarrow\Omega G=1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Remark*
+Biti v isti komponenti je ekvivalenčna relacija (refleksivna, simetrična
+ in tranzitivna).
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $x\in VG$
+\end_inset
+
+ prerezno
+\begin_inset Formula $\Leftrightarrow\Omega\left(G-x\right)>\Omega G$
+\end_inset
+
+.
+
+\begin_inset Formula $e\in EG$
+\end_inset
+
+ prerezna
+\begin_inset Formula $\sim e$
+\end_inset
+
+ most
+\begin_inset Formula $\Leftrightarrow\Omega\left(G-e\right)>\Omega G$
+\end_inset
+
+.
+
+\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
+
+.
+
+\begin_inset Formula $X\subseteq EG$
+\end_inset
+
+ je prerezna množica povezav
+\begin_inset Formula $\Leftrightarrow\Omega\left(G-X\right)>\Omega G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Povezan graf
+\begin_inset Formula $G$
+\end_inset
+
+ je
+\begin_inset Formula $k-$
+\end_inset
+
+povezan
+\begin_inset Formula $\Leftrightarrow\left|VG\right|\geq k+1\wedge\forall X\text{ prerezna}\subseteq VG:\left|X\right|>=k$
+\end_inset
+
+ prerezna.
+ ZDB ima vsaj
+\begin_inset Formula $k+1$
+\end_inset
+
+ vozlišč in
+\series bold
+ne
+\series default
+ vsebuje prerezne množice moči manjše od
+\begin_inset Formula $k$
+\end_inset
+
+.
+ Povezanost grafa
+\begin_inset Formula $G\sim\kappa G$
+\end_inset
+
+ je največji
+\begin_inset Formula $k\in\mathbb{N}$
+\end_inset
+
+, za katerega je
+\begin_inset Formula $G$
+\end_inset
+
+
+\begin_inset Formula $k-$
+\end_inset
+
+povezan ZDB najmanjše število vozlišč, ki jih moramo odstraniti iz grafa,
+ da graf ne bo več povezan.
+\end_layout
+
+\begin_layout Remark*
+\begin_inset Formula $\kappa G=k\Rightarrow G$
+\end_inset
+
+ nima prerezne množice moči
+\begin_inset Formula $<k$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\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_{m,n}=\min\left\{ n,m\right\} $
+\end_inset
+
+,
+\begin_inset Formula $\kappa Q_{n}=n$
+\end_inset
+
+,
+\begin_inset Formula $\kappa G\leq\delta G$
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+\begin_inset Formula $\delta G$
+\end_inset
+
+ je minimalna stopnja vozlišča v grafu
+\begin_inset Formula $G$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+Pojasnite Whitney-ev izrek, ki katekterizira
+\begin_inset Formula $2-$
+\end_inset
+
+povezane grafe.
+ Skicirajte dokaz tega izreka.
+ Zapišite Mengerjev izrek.
+\end_layout
+
+\begin_layout Definition*
+Poti
+\begin_inset Formula $\left[p_{1},p_{2},\dots,p_{n-1},p\right]$
+\end_inset
+
+ in
+\begin_inset Formula $\left[r_{1},r_{2},\dots,r_{m-1},r_{m}\right]$
+\end_inset
+
+ sta notranje disjunktni, če sta disjunktni množici njunih vozlišč izvzemši
+ prvo in zadnje vozlišče.
+\end_layout
+
+\begin_layout Theorem*
+Graf
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $\left|VG\right|\geq2$
+\end_inset
+
+, je
+\begin_inset Formula $2-$
+\end_inset
+
+povezan
+\begin_inset Formula $\Leftrightarrow\forall u,v\in VG\exists$
+\end_inset
+
+ notranje disjunktni
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti.
+\end_layout
+
+\begin_layout Proof
+Dokazujemo ekvivalenco:
+\end_layout
+
+\begin_deeper
+\begin_layout Description
+\begin_inset Formula $\left(\Leftarrow\right)$
+\end_inset
+
+ Po predpostavki za poljubna
+\begin_inset Formula $u,v$
+\end_inset
+
+ obstajata dve notranje disjunktni
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti.
+ Dokazujemo, da je
+\begin_inset Formula $G$
+\end_inset
+
+
+\begin_inset Formula $2-$
+\end_inset
+
+povezan
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+ nima prereznega vozlišča
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+ ne obstaja prerezna množica, ki je singleton
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+množica moči ena
+\end_layout
+
+\end_inset
+
+.
+ Dokažimo, da poljubno
+\begin_inset Formula $x\in VG$
+\end_inset
+
+ ni prerezno, torej da po odstranitvi tega vozlišča še vedno obstaja povezava
+ med poljubnima
+\begin_inset Formula $u,v\in V\left(G-x\right)$
+\end_inset
+
+.
+ Ločimo 3 primere:
+\begin_inset Formula $x$
+\end_inset
+
+ je na prvi
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti,
+\begin_inset Formula $x$
+\end_inset
+
+ je na drugi
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti,
+\begin_inset Formula $x$
+\end_inset
+
+ ni na nobeni izmed
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti.
+ V vsakem primeru sta
+\begin_inset Formula $u,v$
+\end_inset
+
+ v
+\begin_inset Formula $G-x$
+\end_inset
+
+ še vedno v isti povezani komponenti.
+
+\end_layout
+
+\begin_layout Description
+\begin_inset Formula $\left(\Rightarrow\right)$
+\end_inset
+
+ Po predpostavki je
+\begin_inset Formula $G$
+\end_inset
+
+
+\begin_inset Formula $2-$
+\end_inset
+
+povezan.
+ Vzemimo poljubna
+\begin_inset Formula $u,v\in VG$
+\end_inset
+
+.
+ Indukcija po
+\begin_inset Formula $d_{G}\left(u,v\right)$
+\end_inset
+
+:
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Baza:
+\begin_inset Formula $d_{G}\left(u,v\right)=1$
+\end_inset
+
+ (sosednji vozlišči)
+\begin_inset Formula $G-e$
+\end_inset
+
+ je povezan, sicer je RAAPDD
+\begin_inset Formula $uv$
+\end_inset
+
+ most, kar bi bilo v
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+ s predpostavko, ker bi bil en izmed
+\begin_inset Formula $u,v$
+\end_inset
+
+ prerezno, saj ima
+\begin_inset Formula $G$
+\end_inset
+
+ vsaj 3 vozlišča in ima vsaj eden izmed
+\begin_inset Formula $u,v$
+\end_inset
+
+ še enega soseda.
+ Sedaj vemo, da
+\begin_inset Formula $\exists u,v-$
+\end_inset
+
+pot, ki ni
+\begin_inset Formula $uv$
+\end_inset
+
+.
+ Imamo torej dve notranje disjunktni
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti:
+\begin_inset Formula $e$
+\end_inset
+
+ in tisto drugo.
+\end_layout
+
+\begin_layout Standard
+Korak:
+\begin_inset Formula $d_{G}\left(u,v\right)=k\geq2$
+\end_inset
+
+.
+ Naj bo
+\begin_inset Formula $P$
+\end_inset
+
+ najkrajša
+\begin_inset Formula $u,v-$
+\end_inset
+
+pot.
+ Predzadnje vozlišče na njej (tik pred
+\begin_inset Formula $v$
+\end_inset
+
+) naj bo
+\begin_inset Formula $w$
+\end_inset
+
+.
+
+\begin_inset Formula $d_{G}\left(u,w\right)=k-1$
+\end_inset
+
+ in po I.
+ P.
+ obstajata dve notranje disjunktni
+\begin_inset Formula $u,w-$
+\end_inset
+
+poti
+\begin_inset Formula $R$
+\end_inset
+
+ in
+\begin_inset Formula $S$
+\end_inset
+
+.
+ Ločimo primera:
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $v\in VR\cup VS$
+\end_inset
+
+ Tedaj je
+\begin_inset Formula $v$
+\end_inset
+
+ na ciklu, ki ga tvorita poti
+\begin_inset Formula $R$
+\end_inset
+
+ in
+\begin_inset Formula $S$
+\end_inset
+
+ (je na eni izmed poti).
+ Zato obstajata dve notranje disjunktni
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti; ena v eno smer po ciklu, druga v drugo.
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $v\not\in VR\cup VS$
+\end_inset
+
+ Tedaj
+\begin_inset Formula $v$
+\end_inset
+
+ ni na tem ciklu, vendar je sosed
+\begin_inset Formula $w$
+\end_inset
+
+, ki je na ciklu.
+
+\begin_inset Formula $G-w$
+\end_inset
+
+ mora biti povezan, saj smo odstranili le eno vozlišče, torej
+\begin_inset Formula $\exists u,v-$
+\end_inset
+
+pot
+\begin_inset Formula $T$
+\end_inset
+
+.
+ Ločimo primera:
+\end_layout
+
+\begin_deeper
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $T\cap\left(VS\cup VR\right)=\left\{ u\right\} $
+\end_inset
+
+ Našli smo dve notranje disjunktni poti v
+\begin_inset Formula $G$
+\end_inset
+
+:
+\begin_inset Formula $T$
+\end_inset
+
+ in
+\begin_inset Formula $\left[\dots R,v\right]$
+\end_inset
+
+ (
+\begin_inset Formula $R$
+\end_inset
+
+ in
+\begin_inset Formula $wv$
+\end_inset
+
+ povezava).
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left|T\cap\left(VS\cup VR\right)\right|\geq2$
+\end_inset
+
+ Naj bo
+\begin_inset Formula $x$
+\end_inset
+
+ zadnje (kjer je
+\begin_inset Formula $v$
+\end_inset
+
+ konec poti) vozlišče na
+\begin_inset Formula $T$
+\end_inset
+
+, ki je na
+\begin_inset Formula $R\cup S$
+\end_inset
+
+.
+ BSŠ
+\begin_inset Formula $x\in VS$
+\end_inset
+
+.
+
+\begin_inset Formula $x\not=w$
+\end_inset
+
+ po konstrukciji
+\begin_inset Formula $T$
+\end_inset
+
+.
+ Dve poti: po
+\begin_inset Formula $S$
+\end_inset
+
+ do
+\begin_inset Formula $x$
+\end_inset
+
+ in nato po
+\begin_inset Formula $T$
+\end_inset
+
+ do
+\begin_inset Formula $v$
+\end_inset
+
+ ter
+\begin_inset Formula $\left[\dots R,v\right]$
+\end_inset
+
+ (
+\begin_inset Formula $R$
+\end_inset
+
+ in
+\begin_inset Formula $wv$
+\end_inset
+
+ povezava).
+\end_layout
+
+\end_deeper
+\end_deeper
+\end_deeper
+\begin_layout Theorem*
+Menger (posplošitev Whitneya): naj bo
+\begin_inset Formula $G$
+\end_inset
+
+ graf z vsak
+\begin_inset Formula $k+1$
+\end_inset
+
+ vozlišči.
+ Tedaj je
+\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
+
+ paroma notranje disjunktnih
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti.
+\end_layout
+
+\begin_layout Definition*
+Graf je
+\begin_inset Formula $k-$
+\end_inset
+
+ povezan po povezavah, če
+\begin_inset Formula $\nexists$
+\end_inset
+
+ prerezna množica povezav moči
+\begin_inset Formula $<k$
+\end_inset
+
+.
+ Povezanost grafa
+\begin_inset Formula $G$
+\end_inset
+
+ po povezavah (
+\begin_inset Formula $\kappa'G$
+\end_inset
+
+) je največji
+\begin_inset Formula $k$
+\end_inset
+
+, da je
+\begin_inset Formula $G$
+\end_inset
+
+
+\begin_inset Formula $k-$
+\end_inset
+
+povezan po povezavah.
+\end_layout
+
+\begin_layout Theorem*
+Menger':
+\begin_inset Formula $G$
+\end_inset
+
+ je
+\begin_inset Formula $k-$
+\end_inset
+
+povezan po povezavah
+\begin_inset Formula $\Leftrightarrow\forall u,v\in VG\exists k$
+\end_inset
+
+ po povezavah notranje disjunktnih
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+\begin_inset Formula $\forall G\in\mathcal{G}:\kappa G\leq\kappa'G$
+\end_inset
+
+ in
+\begin_inset Formula $\kappa'G\leq\delta G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Dokaze zadnjih treh izrekov najdete na magisteriju.
+\end_layout
+
+\begin_layout Subsection
+Kaj je drevo in kaj je gozd? Katere katekterizacije dreves poznate?
+\end_layout
+
+\begin_layout Definition*
+Gozd je graf brez ciklov.
+ Drevo je povezan gozd.
+ List je vozlišče stopnje 1.
+\end_layout
+
+\begin_layout Lemma
+\begin_inset CommandInset label
+LatexCommand label
+name "lem:Vsako-drevo-z"
+
+\end_inset
+
+Vsako drevo z vsaj dvema vozliščema premore list.
+\end_layout
+
+\begin_layout Proof
+Naj bo
+\begin_inset Formula $T$
+\end_inset
+
+ drevo,
+\begin_inset Formula $v\in VT$
+\end_inset
+
+ poljubno.
+
+\begin_inset Formula $\left|VT\right|\geq2\wedge T$
+\end_inset
+
+ povezan
+\begin_inset Formula $\Rightarrow v$
+\end_inset
+
+ ima soseda
+\begin_inset Formula $v_{1}$
+\end_inset
+
+.
+ Če je
+\begin_inset Formula $v_{1}$
+\end_inset
+
+ edini sosed
+\begin_inset Formula $v$
+\end_inset
+
+, je
+\begin_inset Formula $v$
+\end_inset
+
+ list, sicer je tudi
+\begin_inset Formula $v_{2}\not=v_{1}$
+\end_inset
+
+ sosed
+\begin_inset Formula $v$
+\end_inset
+
+.
+ Če je
+\begin_inset Formula $v$
+\end_inset
+
+ edini sosed
+\begin_inset Formula $v_{2}$
+\end_inset
+
+, je
+\begin_inset Formula $v_{2}$
+\end_inset
+
+ list, sicer je tudi
+\begin_inset Formula $v_{3}$
+\end_inset
+
+ sosed
+\begin_inset Formula $v$
+\end_inset
+
+.
+ Postopek ponavljamo, dokler ne najdemo lista.
+ V grafu ni ciklov in graf je končen, zato se postopek ustavi.
+\end_layout
+
+\begin_layout Lemma
+\begin_inset CommandInset label
+LatexCommand label
+name "lem:-drevo"
+
+\end_inset
+
+
+\begin_inset Formula $T$
+\end_inset
+
+ drevo
+\begin_inset Formula $\Rightarrow\left|ET\right|=\left|VT\right|-1$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+z indukcijo po številu vozlišč:
+\end_layout
+
+\begin_layout Proof
+Baza:
+\begin_inset Formula $\left|VT=1\right|$
+\end_inset
+
+,
+\begin_inset Formula $\left|EG\right|=0$
+\end_inset
+
+ (izolirano vozlišče je drevo)
+\end_layout
+
+\begin_layout Proof
+Korak:
+\begin_inset Formula $T$
+\end_inset
+
+ poljubno drevo
+\begin_inset Formula $\left|VG\right|\geq2$
+\end_inset
+
+.
+
+\begin_inset Formula $v\in VT$
+\end_inset
+
+ naj bo list v
+\begin_inset Formula $T$
+\end_inset
+
+ po lemi
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "lem:Vsako-drevo-z"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+.
+ Po I.
+ P.
+ je
+\begin_inset Formula $\left|E\left(T-v\right)\right|=\left|V\left(T-v\right)\right|-1$
+\end_inset
+
+, po konstrukciji
+\begin_inset Formula $T-v$
+\end_inset
+
+ pa je
+\begin_inset Formula $\left|E\left(T-v\right)\right|=\left|ET\right|-1$
+\end_inset
+
+,
+\begin_inset Formula $\left|V\left(T-v\right)\right|=\left|VT\right|-1$
+\end_inset
+
+, torej
+\begin_inset Formula $\left|ET\right|=\left|VT\right|-1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Lemma
+\begin_inset CommandInset label
+LatexCommand label
+name "lem:lema3drevesa-enaciklu-g-e-povezan"
+
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ povezan,
+\begin_inset Formula $e\in EG$
+\end_inset
+
+ leži na ciklu
+\begin_inset Formula $\Rightarrow G-e$
+\end_inset
+
+ povezan.
+\end_layout
+
+\begin_layout Proof
+Trdimo, da v
+\begin_inset Formula $G-e\exists u,v-$
+\end_inset
+
+pot.
+ Ker je
+\begin_inset Formula $G$
+\end_inset
+
+ povezan,
+\begin_inset Formula $\exists u,v-$
+\end_inset
+
+pot
+\begin_inset Formula $P$
+\end_inset
+
+ v
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Če
+\begin_inset Formula $e\not\in P$
+\end_inset
+
+, ta pot obstaja tudi v
+\begin_inset Formula $G-e$
+\end_inset
+
+.
+ Če
+\begin_inset Formula $e\in P$
+\end_inset
+
+, očitno dobimo pot tako, da
+\begin_inset Formula $e$
+\end_inset
+
+ v
+\begin_inset Formula $P$
+\end_inset
+
+ nadomestimo s preostankom cikla, na katerem leži
+\begin_inset Formula $e$
+\end_inset
+
+ v
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Lemma
+\begin_inset CommandInset label
+LatexCommand label
+name "lem:-povezan-."
+
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ povezan
+\begin_inset Formula $\Rightarrow\left|EG\right|\geq\left|VG\right|-1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Če je
+\begin_inset Formula $G$
+\end_inset
+
+ drevo, velja enakost po lemi
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "lem:-drevo"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+, sicer
+\begin_inset Formula $G$
+\end_inset
+
+ premore cikel.
+ Po lemi
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "lem:lema3drevesa-enaciklu-g-e-povezan"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+
+\begin_inset Formula $\exists e\in EG\ni:G-e$
+\end_inset
+
+ povezan.
+ Odstranjevanje povezav iz ciklov ponavljamo, dokler ne dobimo drevesa
+\begin_inset Formula $T$
+\end_inset
+
+.
+ Velja
+\begin_inset Formula $VT=VG$
+\end_inset
+
+ (*) in
+\begin_inset Formula $\left|ET\right|<\left|EG\right|$
+\end_inset
+
+ (**).
+ Torej:
+\begin_inset Formula $\left|VG\right|-1\overset{\text{(*)}}{=}\left|VT\right|-1\overset{\text{lema \ref{lem:-drevo}}}{=}\left|ET\right|\overset{\text{(**)}}{<}\left|EG\right|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Theorem*
+Karakterizacija dreves.
+ NTSE za graf
+\begin_inset Formula $G$
+\end_inset
+
+:
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:-drevo"
+
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ drevo
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:-pot-ZDB"
+
+\end_inset
+
+
+\begin_inset Formula $\forall u,v\in VG\exists!$
+\end_inset
+
+
+\begin_inset Formula $u,v-$
+\end_inset
+
+pot ZDB za vsak par vozlišč obstaja enolična pot
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:-povezan-"
+
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ povezan
+\begin_inset Formula $\wedge\forall e\in EG:e$
+\end_inset
+
+ most
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:-povezan"
+
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ povezan
+\begin_inset Formula $\wedge\left|EG\right|=\left|VG\right|-1$
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Proof
+Dokazujemo ekvivalenco:
+\end_layout
+
+\begin_deeper
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(\ref{enu:-drevo}\Rightarrow\ref{enu:-pot-ZDB}\right)$
+\end_inset
+
+ PDDRAA
+\begin_inset Formula $\exists$
+\end_inset
+
+ dve različni
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti za neka
+\begin_inset Formula $u,v\in VG$
+\end_inset
+
+.
+ Tedaj graf premore cikel
+\begin_inset Formula $\Rightarrow$
+\end_inset
+
+ ni gozd
+\begin_inset Formula $\Rightarrow$
+\end_inset
+
+ ni drevo
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+.
+ PDDRAA
+\begin_inset Formula $\nexists$
+\end_inset
+
+
+\begin_inset Formula $u,v-$
+\end_inset
+
+pot za neka
+\begin_inset Formula $u,v\in VG\Rightarrow\Omega G\not=1\Rightarrow$
+\end_inset
+
+ ni drevo
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(\ref{enu:-pot-ZDB}\Rightarrow\ref{enu:-povezan-}\right)$
+\end_inset
+
+ PDDRAA
+\begin_inset Formula $\exists uv\in EG\ni:$
+\end_inset
+
+ ni most
+\begin_inset Formula $\Rightarrow\exists u,v-$
+\end_inset
+
+pot v
+\begin_inset Formula $G-e\Rightarrow\exists$
+\end_inset
+
+ dve različni
+\begin_inset Formula $u,v-$
+\end_inset
+
+poti v
+\begin_inset Formula $G$
+\end_inset
+
+ (
+\begin_inset Formula $uv$
+\end_inset
+
+ in tista v
+\begin_inset Formula $G-e$
+\end_inset
+
+)
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(\ref{enu:-povezan-}\Rightarrow\ref{enu:-povezan}\right)$
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ povezan
+\begin_inset Formula $\Rightarrow G$
+\end_inset
+
+ povezan velja vedno.
+ Dokažimo
+\begin_inset Formula $\left|EG\right|=\left|VG\right|-1$
+\end_inset
+
+ z indukcijo po številu vozlišč:
+\end_layout
+
+\begin_deeper
+\begin_layout Standard
+Baza: V
+\begin_inset Formula $K_{2}$
+\end_inset
+
+ je edina povezava most in
+\begin_inset Formula $\left|EK_{2}\right|=2-1=1=\left|VK_{2}\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Korak:
+\begin_inset Formula $e\in EG$
+\end_inset
+
+ poljuben:
+\begin_inset Formula $\Omega\left(G-e\right)=2$
+\end_inset
+
+, dve komponenti
+\begin_inset Formula $G-e$
+\end_inset
+
+ naj bosta
+\begin_inset Formula $G_{1}$
+\end_inset
+
+ in
+\begin_inset Formula $G_{2}$
+\end_inset
+
+.
+ Slednja sta povezana in za njiju velja, da je vsaka povezava most in sta
+ manjša grafa.
+ Po I.
+ P.
+ velja
+\begin_inset Formula $\left|EG_{1}\right|=\left|VG_{1}\right|-1$
+\end_inset
+
+ in
+\begin_inset Formula $\left|EG_{2}\right|=\left|VG_{2}\right|-1$
+\end_inset
+
+.
+ Velja
+\begin_inset Formula $\left|EG\right|=\left|EG_{1}\right|+\left|EG_{2}\right|+1=\left|VG_{1}\right|-1+\left|VG_{2}\right|-1+1=\left|VG_{1}\right|+\left|VG_{2}\right|-1=\left|VG\right|-1$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(\ref{enu:-povezan}\Rightarrow\ref{enu:-pot-ZDB}\right)$
+\end_inset
+
+ PDDRAA
+\begin_inset Formula $G$
+\end_inset
+
+ premore cikel
+\begin_inset Formula $\overset{\text{lema \ref{lem:lema3drevesa-enaciklu-g-e-povezan}}}{\Rightarrow}$
+\end_inset
+
+ če mu odstranimo povezavo s cikla, bo ostal povezan.
+ Obenem zaradi velja
+\begin_inset Formula $\left|E\left(G-e\right)\right|=\left|V\left(G-e\right)\right|-2$
+\end_inset
+
+, kar je v
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+ z lemo
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "lem:-povezan-."
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+ (
+\begin_inset Formula $G$
+\end_inset
+
+ povezan, toda ne velja implikacija).
+\end_layout
+
+\end_deeper
+\begin_layout Subsection
+Kaj je vpeto drevo grafa? Kateri grafi premorejo vpeta drevesa? Kako lahko
+ rekurzivno določimo število vpetih dreves povezanega grafa?
+\end_layout
+
+\begin_layout Definition*
+Podgraf
+\begin_inset Formula $H$
+\end_inset
+
+ grafa
+\begin_inset Formula $G$
+\end_inset
+
+ je vpet, če velja
+\begin_inset Formula $VP=VG$
+\end_inset
+
+.
+ (Lahko pa ima ima
+\begin_inset Formula $G$
+\end_inset
+
+ povezave, ki jih
+\begin_inset Formula $H$
+\end_inset
+
+ nima).
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Vpeto drevo grafa
+\begin_inset Formula $G$
+\end_inset
+
+ je vpet podgraf, ki je drevo.
+\end_layout
+
+\begin_layout Theorem*
+\begin_inset Formula $G$
+\end_inset
+
+ povezan
+\begin_inset Formula $\Leftrightarrow G$
+\end_inset
+
+ premore vpeto drevo.
+\end_layout
+
+\begin_layout Proof
+\begin_inset Formula $\left(\Leftarrow\right)$
+\end_inset
+
+ očitno.
+
+\begin_inset Formula $\left(\Rightarrow\right)$
+\end_inset
+
+: Če je
+\begin_inset Formula $G$
+\end_inset
+
+ drevo, je sam sebi vpeto drevo, sicer vsebuje cikel in iterativno uporabljamo
+ lemo
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "lem:lema3drevesa-enaciklu-g-e-povezan"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+, dokler ne konstruiramo vpetega drevesa.
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $\tau G$
+\end_inset
+
+ naj bo število vpetih dreves grafa
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Remark*
+\begin_inset Formula $T$
+\end_inset
+
+ drevo
+\begin_inset Formula $\Rightarrow\tau T=1$
+\end_inset
+
+,
+\begin_inset Formula $\Omega G>1\Rightarrow\tau G=0$
+\end_inset
+
+,
+\begin_inset Formula $\tau C_{n}=n$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Z
+\begin_inset Formula $G/e$
+\end_inset
+
+ označimo skrčitev povezave
+\begin_inset Formula $e$
+\end_inset
+
+ v multigrafu
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+V multigrafu se ista povezava lahko pojavi večkrat.
+\end_layout
+
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+.
+ To je enako kot skrčitev povezave v grafu (
+\begin_inset Formula $G\backslash e$
+\end_inset
+
+), le da ne odstranimo večkratnih vzporednih povezav.
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $G$
+\end_inset
+
+ povezan,
+\begin_inset Formula $e\in EG\Rightarrow\tau G=\tau\left(G-e\right)+\tau\left(G/e\right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Naj bo
+\begin_inset Formula $T$
+\end_inset
+
+ vpeto drevo v
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Naj bo
+\begin_inset Formula $e\in EG$
+\end_inset
+
+ poljuben fiksen.
+ Vpetih dreves, za katere
+\begin_inset Formula $e\not\in T$
+\end_inset
+
+, je
+\begin_inset Formula $\tau\left(G-e\right)$
+\end_inset
+
+.
+ Vpetih dreves, za katere
+\begin_inset Formula $e\in T$
+\end_inset
+
+, je
+\begin_inset Formula $\tau\left(G/e\right)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Rekurzivno torej določamo število vpetih dreves grafa z zgornjo trditvijo
+ tako, da izbiramo poljubne povezave in jih ožamo ter odstranjujemo in nato
+ seštejemo
+\begin_inset Formula $\tau$
+\end_inset
+
+ teh dveh operacij.
+\end_layout
+
+\begin_layout Subsection
+Kaj je Laplaceova matrika multigrafa? Kaj pravi Kirchoffov izrek o številu
+ vpetih dreves multigrafa?
+\end_layout
+
+\begin_layout Definition*
+Laplaceova matrika
+\begin_inset Formula $LG$
+\end_inset
+
+ je kvadratna matrika dimenzije
+\begin_inset Formula $n$
+\end_inset
+
+, katere vrstice in stolpci so indeksirani z vozlišči multigrafa
+\begin_inset Formula $G$
+\end_inset
+
+ in velja
+\begin_inset Formula
+\[
+LG_{ij}=\begin{cases}
+\deg_{G}v & ;i=j\\
+-\left(\text{število povezav med \ensuremath{v_{i}} in \ensuremath{v_{j}}}\right) & ;i\not=j
+\end{cases}
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Kirchoff: Če je
+\begin_inset Formula $G$
+\end_inset
+
+ povezan multigraf, potem je
+\begin_inset Formula $\tau G=\det\left(LG\text{ brez \ensuremath{i}tega stolpca in \ensuremath{i}te vrstice}\right)$
+\end_inset
+
+ za poljuben
+\begin_inset Formula $i$
+\end_inset
+
+.
+ ZDB
+\begin_inset Formula $\tau G=\det LG_{i,i}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsection
+Kaj pomeni, da je graf Eulerjev? Kako karakteriziramo Eulerjeve grafe? Skicirajt
+e dokaz slednjega rezultata.
+\end_layout
+
+\begin_layout Definition*
+Sprehod v multigrafu je Eulerjev, če vsebuje vse povezave in sicer vsako
+ zgolj enkrat.
+
+\series bold
+Sklenjen
+\series default
+ Eulerjev sprehod je Eulerjev obhod.
+ Graf je Eulerjev, če premore Eulerjev obhod.
+\end_layout
+
+\begin_layout Theorem*
+\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 Proof
+\begin_inset Formula $\left(\Rightarrow\right)$
+\end_inset
+
+ očitno.
+
+\begin_inset Formula $\left(\Leftarrow\right)$
+\end_inset
+
+:
+\begin_inset Formula $\forall v\in VG:\deg_{G}v$
+\end_inset
+
+ sod
+\begin_inset Formula $\Rightarrow$
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+ premore cikel.
+ Indukcija po številu povezav:
+\end_layout
+
+\begin_layout Proof
+Baza: Izolirano vozlišče, multigraf
+\begin_inset Formula $VG=\left\{ u,v\right\} ,EG=\left\{ uv,uv\right\} $
+\end_inset
+
+ in
+\begin_inset Formula $C_{3}$
+\end_inset
+
+ so vsi Eulerjevi.
+\end_layout
+
+\begin_layout Proof
+Korak: Naj bo
+\begin_inset Formula $\left|VG\right|\geq4$
+\end_inset
+
+.
+
+\begin_inset Formula $G$
+\end_inset
+
+ gotovo premore cikel
+\begin_inset Formula $C$
+\end_inset
+
+, ker je povezan in nima listov (ni drevo).
+ Naj bo
+\begin_inset Formula $H\coloneqq G-EC$
+\end_inset
+
+.
+
+\begin_inset Formula $\forall u\in VC:\deg_{H}u=\deg_{G}u-2$
+\end_inset
+
+,
+\begin_inset Formula $\forall u\not\in VC:\deg_{H}u=\deg_{G}u$
+\end_inset
+
+
+\begin_inset Formula $\Rightarrow\forall v\in H:\deg_{H}v$
+\end_inset
+
+ sod
+\begin_inset Formula $\Rightarrow$
+\end_inset
+
+ vsaka komponenta
+\begin_inset Formula $H$
+\end_inset
+
+ je Eulerjev graf po I.
+ P., saj je manjši graf.
+
+\begin_inset Formula $G$
+\end_inset
+
+ je tudi Eulerjev, obhodimo ga lahko po ciklu
+\begin_inset Formula $C$
+\end_inset
+
+; vsakič, ko naletimo na vozlišče, ki je del komponente
+\begin_inset Formula $H$
+\end_inset
+
+, jo obhodimo in nadaljujemo pot po ciklu.
+\end_layout
+
+\begin_layout Paragraph*
+Fleuryjev algoritem
+\end_layout
+
+\begin_layout Standard
+sprejme graf in vrne obhod
+\end_layout
+
+\begin_layout Enumerate
+Začnemo v poljubni povezavi
+\end_layout
+
+\begin_layout Enumerate
+Ko povezavo prehodimo, jo izbrišemo
+\end_layout
+
+\begin_layout Enumerate
+Postopek nadaljujemo in pri tem pazimo le na to, da gremo na most le v primeru,
+ če ni druge možnosti.
+\end_layout
+
+\begin_layout Theorem*
+Če je
+\begin_inset Formula $G$
+\end_inset
+
+ Eulerjev graf, potem Fleuryjev algoritem vrne Eulerjev obhod.
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+dodaj dekompozicijo in dekompozicijo v cikle
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+Kdaj je graf Hamiltonov? Navedite in pojasnite potrebni pogoj z razpadom
+ grafa za obstoj Hamiltonovega cikla v grafu.
+\end_layout
+
+\begin_layout Definition*
+
+\series bold
+Hamiltonov cikel
+\series default
+v grafu je cikel, ki vsebuje vsa vozlišča grafa ZDB Hamiltonov cikel je
+ vpet podgraf, ki je cikel.
+
+\series bold
+Graf je Hamiltonov
+\series default
+, če premore Hamiltonov cikel.
+
+\series bold
+Hamiltonova pot
+\series default
+ v grafu je pot, ki vsebuje vsa vozlišča grafa ZDB vpet podgraf, ki je pot.
+\end_layout
+
+\begin_layout Theorem*
+\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
+
+.
+ (potreben pogoj za obstoj Hamiltonovega cikla)
+\end_layout
+
+\begin_layout Proof
+Naj bo
+\begin_inset Formula $VG=\left\{ v_{1},\dots,v_{n}\right\} $
+\end_inset
+
+ Hamiltonov.
+ BSŠ naj bo
+\begin_inset Formula $\left[v_{1},\dots,v_{n}\right]$
+\end_inset
+
+ Hamiltonov cikel.
+ Skica dokaza: Naj bosta
+\begin_inset Formula $v_{i},v_{j}\in S,i<j$
+\end_inset
+
+.
+ Tedaj
+\begin_inset Formula $G-S$
+\end_inset
+
+ razbije
+\begin_inset Formula $G$
+\end_inset
+
+ na dva podgrafa:
+\begin_inset Formula $K_{1}\left\{ v_{i+1},\dots,v_{j-1}\right\} $
+\end_inset
+
+ in
+\begin_inset Formula $K_{2}=\left(VG\cap\left\{ v_{i},v_{j}\right\} \right)\cap K_{1}=\left\{ v_{j+1},\dots,v_{n},v_{1},\dots,v_{i-1}\right\} $
+\end_inset
+
+.
+ Če
+\begin_inset Formula $i=j-1$
+\end_inset
+
+, je ena podgraf prazen, če
+\begin_inset Formula $n=3$
+\end_inset
+
+ prav tako.
+ Podgrafa sta lahko povezana in tvorita skupno komponento, lahko pa nista
+ in tvorita dve komponenti.
+ Toda z odstranjevanjem
+\begin_inset Formula $\left|S\right|$
+\end_inset
+
+ vozlišč iz cikla lahko napravimo največ
+\begin_inset Formula $\left|S\right|$
+\end_inset
+
+ komponent.
+\end_layout
+
+\begin_layout Remark*
+Izrek uporabimo v kontrapoziciji:
+\begin_inset Formula $\exists S\subseteq VG\ni:\Omega\left(G-S\right)>\left|S\right|\Rightarrow G$
+\end_inset
+
+ ni Hamiltonov.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $G$
+\end_inset
+
+ vsebuje prerezno vozlišče
+\begin_inset Formula $\Rightarrow G$
+\end_inset
+
+ ni Hamiltonov.
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $K_{m,n}$
+\end_inset
+
+ Hamiltonov
+\begin_inset Formula $\Leftrightarrow m=n$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+\begin_inset Formula $\left(\Rightarrow\right)$
+\end_inset
+
+ Uporabimo izrek o potrebnem pogoju.
+ RAAPDD BSŠ
+\begin_inset Formula $m>n$
+\end_inset
+
+:
+\begin_inset Formula $\Omega\left(G-n\right)=m$
+\end_inset
+
+, kar vodi v
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+.
+
+\begin_inset Formula $\left(\Leftarrow\right)$
+\end_inset
+
+ Očitno lahko skiciramo Hamiltonov cikel.
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $G$
+\end_inset
+
+ dvodelen z razdelitvijo
+\begin_inset Formula $\left(A,B\right)$
+\end_inset
+
+,
+\begin_inset Formula $\left|A\right|\not=\left|B\right|\Rightarrow G$
+\end_inset
+
+ ni Hamiltonov.
+\end_layout
+
+\begin_layout Subsection
+Navedite Orejev zadostni pogoj za obstoj Hamiltonovega cikla v grafu.
+ Skicirajte dokaz tega izreka.
+\end_layout
+
+\begin_layout Theorem*
+Ore:
+\begin_inset Formula $G$
+\end_inset
+
+ graf,
+\begin_inset Formula $\left|VG\right|\geq3$
+\end_inset
+
+,
+\begin_inset Formula $\left(\forall u,v\in VG:uv\not\in EG\Rightarrow\deg u+\deg v\geq\left|VG\right|\right)\Rightarrow G$
+\end_inset
+
+ Hamiltonov.
+ ZDB če za vsak par nesosednjih vozlišč v grafu z vsaj tremi vozlišči velja
+
+\begin_inset Formula $\deg u+\deg v\geq\left|VG\right|$
+\end_inset
+
+, je graf Hamiltonov.
+\end_layout
+
+\begin_layout Proof
+Dokaz z metodo najmanjšega protiprimera.
+ RAAPDD izrek ne velja.
+ Tedaj
+\begin_inset Formula $\exists G$
+\end_inset
+
+, da predpostavka velja, zaključek pa ne.
+ Med vsemi takimi grafi izberimo tiste z najmanj vozlišči, izmed njih pa
+ enega izmed tistih, ki imajo največ povezav, in ga fiksiramo.
+ Naj bo to graf
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Zanj velja:
+\end_layout
+
+\begin_deeper
+\begin_layout Itemize
+\begin_inset Formula $\forall u,v\in VG:uv\not\in EG\Rightarrow\deg u+\deg v\geq\left|VG\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Itemize
+\begin_inset Formula $G$
+\end_inset
+
+ ni Hamiltonov
+\begin_inset Formula $\Rightarrow G$
+\end_inset
+
+ gotovo ni polni graf
+\begin_inset Formula $\Rightarrow\exists u,v\in VG\ni:uv\not\in EG$
+\end_inset
+
+.
+ Naj bo
+\begin_inset Formula $H$
+\end_inset
+
+ graf, da velja
+\begin_inset Formula $VH\coloneqq VG$
+\end_inset
+
+ in
+\begin_inset Formula $EH\coloneqq EG\cup uv$
+\end_inset
+
+.
+ Zanj še vedno velja prejšnja točka, zaradi izbire
+\begin_inset Formula $G$
+\end_inset
+
+ (največ povezav) pa ni več protiprimer za izrek, zato je Hamiltonov.
+ Vsak Hamiltonov cikel v
+\begin_inset Formula $H$
+\end_inset
+
+ vsebuje
+\begin_inset Formula $uv$
+\end_inset
+
+, sicer bi obstajal že v
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Vseeno pa
+\begin_inset Formula $G$
+\end_inset
+
+ premore Hamiltonovo pot, saj smo do cikla namreč dodali le eno povezavo.
+ Naj bo
+\begin_inset Formula $\left[u=v_{1},v_{2},\dots,v_{n-1},v_{n}=v\right]$
+\end_inset
+
+ Hamiltonov cikel v
+\begin_inset Formula $H$
+\end_inset
+
+.
+ Vpeljimo množici
+\begin_inset Formula $S=\left\{ v_{i},uv_{i+1}\in EG\right\} $
+\end_inset
+
+ (ZDB predhodniki sosedov
+\begin_inset Formula $u$
+\end_inset
+
+ na Hamiltonovi poti v
+\begin_inset Formula $G$
+\end_inset
+
+) in
+\begin_inset Formula $T=\left\{ v_{i},vv_{i}\in EG\right\} $
+\end_inset
+
+ (ZDB sosedje
+\begin_inset Formula $v$
+\end_inset
+
+ na Hamiltonovi poti v
+\begin_inset Formula $G$
+\end_inset
+
+).
+ Velja
+\begin_inset Formula $\left|S\cup T\right|=\left|S\right|+\left|T\right|-\left|S\cap T\right|$
+\end_inset
+
+, torej
+\begin_inset Formula $\left|S\cup T\right|+\left|S\cup T\right|=\left|S\right|+\left|T\right|=\deg_{G}u+\deg_{G}v\overset{\text{predpostavka}}{\geq}\left|VG\right|=n$
+\end_inset
+
+.
+ Toda ker je
+\begin_inset Formula $\left|S\cup T\right|=\left|VG\right|$
+\end_inset
+
+,
+\begin_inset Formula $\left|S\cap T\right|\not=\emptyset$
+\end_inset
+
+, torej ima
+\begin_inset Formula $v$
+\end_inset
+
+ soseda iz
+\begin_inset Formula $S$
+\end_inset
+
+ (recimo mu
+\begin_inset Formula $v_{i}$
+\end_inset
+
+), torej lahko konstruiramo Hamiltonov cikel v
+\begin_inset Formula $G$
+\end_inset
+
+:
+\begin_inset Formula $\left[u=v_{1},v_{2},\dots,v_{i},v_{n}=v,v_{n-1},\dots,v_{i+1},v_{1}=u\right]$
+\end_inset
+
+ (
+\begin_inset Formula $v_{i+1}$
+\end_inset
+
+ je namreč po konstrukciji
+\begin_inset Formula $S$
+\end_inset
+
+ sosed
+\begin_inset Formula $u$
+\end_inset
+
+), kar vodi v
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Subsection
+\begin_inset CommandInset label
+LatexCommand label
+name "subsec:Kaj-so-ravninski"
+
+\end_inset
+
+Kaj so ravninski grafi? Kaj so lica ravninske vložitve grafa in čemu je
+ enaka vsota dolžin vseh lic ravninske vložitve grafa? Kako lahko omejimo
+ število povezav ravninskega grafa s pomočjo njegove ožine?
+\end_layout
+
+\begin_layout Definition*
+Graf
+\begin_inset Formula $G$
+\end_inset
+
+ ravninski
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+ lahko ga narišemo v ravnino tako, da se nobeni povezavi ne križata.
+ Ravninski graf skupaj z ustrezno risbo (vložitvijo) je graf, vložen v ravnino.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $K_{2,3}$
+\end_inset
+
+ je ravninski,
+\begin_inset Formula $K_{3,3}$
+\end_inset
+
+ ni ravninski.
+\end_layout
+
+\begin_layout Theorem*
+Jordan: Sklenjena enostavna krivulja (t.
+ j.
+ taka, ki same sebe ne križa) v ravnini razdeli ravnino v notranjost, zunanjost
+ in krivuljo samo.
+\end_layout
+
+\begin_layout Definition*
+Naj bo
+\begin_inset Formula $G$
+\end_inset
+
+ ravninski, vložen v ravnino.
+ Sklenjena območja v ravnini, dobljena tako, da iz risbe odstranimo točke,
+ ki ustrezajo vozliščem in povezavam, imenujemo
+\series bold
+lica vložitve
+\series default
+.
+ S
+\begin_inset Formula $FG$
+\end_inset
+
+ označimo množico lič vložitve.
+ Seveda je tudi zunanje/neomejeno območje lice.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\left|FQ_{3}\right|=6$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Remark*
+\begin_inset Formula $G$
+\end_inset
+
+ lahko vložimo v ravnino
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+ lahko ga vložimo na sfero.
+\end_layout
+
+\begin_layout Definition*
+Dolžina lica
+\begin_inset Formula $F$
+\end_inset
+
+
+\begin_inset Formula $(\text{\ensuremath{\ell F}}),$
+\end_inset
+
+je število povezav, ki jih prehodimo, ko obhodimo lice\SpecialChar endofsentence
+
+\end_layout
+
+\begin_layout Remark*
+Vsako drevo je ravninski graf.
+ Ima eno lice, katerega dolžina je
+\begin_inset Formula $2\left|ET\right|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Definition*
+Ožina grafa
+\begin_inset Formula $G$
+\end_inset
+
+,
+\begin_inset Formula $gG$
+\end_inset
+
+, je dolžina najkrajšega cikla v
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Če je
+\begin_inset Formula $G$
+\end_inset
+
+ gozd, je
+\begin_inset Formula $gG\coloneqq\infty$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Claim*
+Če je
+\begin_inset Formula $G$
+\end_inset
+
+ ravninsli graf, vložen v ravnino, velja
+\begin_inset Formula
+\[
+\sum_{F\in FG}\ell F=2\left|EG\right|
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Claim*
+Naj
+\begin_inset Formula $G$
+\end_inset
+
+ premore cikel.
+ Naj bo
+\begin_inset Formula $F\in FG$
+\end_inset
+
+.
+
+\begin_inset Formula $\ell F\geq gG$
+\end_inset
+
+.
+
+\begin_inset Formula $2\left|EG\right|=\sum_{F\in FG}\ell F\geq\sum_{F\in FG}gG=gG\left|FG\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Claim*
+Posledično: Če je
+\begin_inset Formula $G$
+\end_inset
+
+ ravninski graf z vsaj enim ciklom in je vložen v ravnino, je
+\begin_inset Formula $\left|EG\right|\geq\frac{gG}{2}\left|FG\right|$
+\end_inset
+
+(*).
+\end_layout
+
+\begin_layout Subsection
+Kaj pravi Eulerjeva formula za ravninske grafe? Skicirajte njen dokaz.
+ Katere posledice Eulerjeve formule poznate?
+\end_layout
+
+\begin_layout Theorem*
+Eulerjeva formula: Če je
+\begin_inset Formula $G$
+\end_inset
+
+ ravninski vložen v ravnino, velja
+\begin_inset Formula $\left|VG\right|-\left|EG\right|+\left|FG\right|=1+\Omega G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+Graf
+\begin_inset Quotes gld
+\end_inset
+
+tri hiše
+\begin_inset Quotes grd
+\end_inset
+
+:
+\begin_inset Formula $\left|VG\right|=15$
+\end_inset
+
+,
+\begin_inset Formula $\left|EG\right|=18$
+\end_inset
+
+,
+\begin_inset Formula $\left|FG\right|=7$
+\end_inset
+
+,
+\begin_inset Formula $\Omega G=3$
+\end_inset
+
+,
+\begin_inset Formula $15+16+7=1+3$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Dokažimo najprej za povezan multigraf
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Dokazujemo
+\begin_inset Formula $\left|VG\right|-\left|EG\right|+\left|FG\right|=2$
+\end_inset
+
+.
+ Indukcija po številu vozlišč:
+\end_layout
+
+\begin_layout Proof
+Baza: Izolirano vozlišče:
+\begin_inset Formula $\left|VG\right|=1$
+\end_inset
+
+,
+\begin_inset Formula $\left|EG\right|=0+z$
+\end_inset
+
+,
+\begin_inset Formula $\left|FG\right|=1+z$
+\end_inset
+
+, kjer je
+\begin_inset Formula $z$
+\end_inset
+
+ število zank (za navaden graf
+\begin_inset Formula $z=0$
+\end_inset
+
+).
+ Drži.
+\end_layout
+
+\begin_layout Proof
+Korak: Naj bo
+\begin_inset Formula $e\in EG$
+\end_inset
+
+ poljubna.
+ Skrčimo jo (kot v multigrafu).
+
+\begin_inset Formula $\left|V\left(G/e\right)\right|=\left|VG\right|-1$
+\end_inset
+
+,
+\begin_inset Formula $\left|E\left(G/e\right)\right|=\left|EG\right|-1$
+\end_inset
+
+,
+\begin_inset Formula $\left|F\left(G/e\right)\right|=\left|FE\right|$
+\end_inset
+
+.
+ Velja
+\begin_inset Formula $\left|VG\right|-\left|EG\right|+\left|FG\right|=2$
+\end_inset
+
+, saj po I.
+ P.
+ velja
+\begin_inset Formula $\left|V\left(G/e\right)\right|+1-\left|E\left(G/e\right)\right|-1+\left|F\left(G/e\right)\right|=2$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Sedaj dokažimo še za nepovezan multigraf
+\begin_inset Formula $G$
+\end_inset
+
+ z
+\begin_inset Formula $\Omega G$
+\end_inset
+
+ komponentami.
+ Grafu lahko dodamo
+\begin_inset Formula $\Omega G-1$
+\end_inset
+
+ povezav, da ga povežemo, s čimer ne spremenimo niti
+\begin_inset Formula $\left|FG\right|$
+\end_inset
+
+ niti
+\begin_inset Formula $\left|VG\right|$
+\end_inset
+
+.
+ Če je
+\begin_inset Formula $E$
+\end_inset
+
+ množica povezav, ki jo moramo dodati, velja
+\begin_inset Formula $\left|VG\right|-\left|EG\cup E\right|+\left|FG\right|=2=\left|VG\right|-\left|EG\right|-\Omega G+1+\left|FG\right|\Rightarrow\left|VG\right|-\left|EG\right|+\left|FG\right|=2-1+\Omega G=1+\Omega G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Theorem*
+Za ravninski graf z vsaj tremi vozlišči velja
+\begin_inset Formula $\left|EG\right|\leq3\left|VG\right|-6$
+\end_inset
+
+, če je slednji brez trikotnikov, a ima cikel, pa celo
+\begin_inset Formula $\left|EG\right|\leq2\left|VG\right|-4$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Dokažimo za povezan ravninski graf, sicer mu lahko samo dodamo povezave
+ in ga povežemo.
+ Ločimo primera:
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(G\text{ drevo}\right)$
+\end_inset
+
+
+\begin_inset Formula $\left|EG\right|=\left|VG\right|-1$
+\end_inset
+
+ (karakterizacija dreves)
+\begin_inset Formula $\overset{?}{\leq}3\left|VG\right|-6$
+\end_inset
+
+.
+ Drži, kajti
+\begin_inset Formula $\left|VG\right|\geq3$
+\end_inset
+
+.
+\end_layout
+
+\begin_deeper
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(G\text{ premore cikel}\right)$
+\end_inset
+
+ Po Eulerjevi formuli velja
+\begin_inset Formula
+\[
+2=\left|VG\right|-\left|EG\right|+\left|FG\right|\overset{\text{(*) iz \ref{subsec:Kaj-so-ravninski}}}{\leq}\left|VG\right|-\left|EG\right|+\frac{2\left|EG\right|}{gG}
+\]
+
+\end_inset
+
+
+\begin_inset Formula
+\[
+2\leq\left|VG\right|-\left|EG\right|+\frac{2\left|EG\right|}{gG}
+\]
+
+\end_inset
+
+
+\begin_inset Formula
+\[
+2-\left|VG\right|\leq\left|EG\right|\left(\frac{2}{gG}-1\right)\quad\quad\quad\quad/^{-1}
+\]
+
+\end_inset
+
+
+\begin_inset Formula
+\[
+\left|VG\right|-2\geq\left|EG\right|\left(1-\frac{2}{gG}\right)=\left|EG\right|\left(\frac{gG-2}{gG}\right)
+\]
+
+\end_inset
+
+
+\begin_inset Formula
+\[
+\left(\left|VG\right|-2\right)\frac{gG}{gG-2}\geq\left|EG\right|
+\]
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Formula $\frac{gG}{gG-2}$
+\end_inset
+
+ je največ 3 in to tedaj, ko graf premore trikotnik.
+ Če za vse večje
+\begin_inset Formula $gG$
+\end_inset
+
+ bo ta ulomek manjši, torej lahko levo stran omejimo navzdol:
+\begin_inset Formula $3\left|VG\right|-6\geq\left(\left|VG\right|-2\right)\frac{gG}{gG-2}\geq\left|EG\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+Če pa graf ne premore trikotnika, a ima cikel, pa je
+\begin_inset Formula $\frac{gG}{gG-2}=2$
+\end_inset
+
+ in levo stran strožje omejimo navzgor in velja
+\begin_inset Formula $2\left|VG\right|-4\geq\left|EG\right|$
+\end_inset
+
+.
+
+\end_layout
+
+\end_deeper
+\begin_layout Subsection
+Kaj je kromatično število
+\begin_inset Formula $\chi\left(G\right)$
+\end_inset
+
+ grafa
+\begin_inset Formula $G$
+\end_inset
+
+? Pojasnite požrešni algoritem barvanja grafa.
+ Kako lahko z njegovo pomočjo navzgor omejimo
+\begin_inset Formula $\chi\left(G\right)$
+\end_inset
+
+?
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $k-$
+\end_inset
+
+barvanje grafa
+\begin_inset Formula $G$
+\end_inset
+
+ je preslikava
+\begin_inset Formula $C:VG\to\left\{ 1..k\right\} $
+\end_inset
+
+, za katero velja
+\begin_inset Formula $uv\in EG\Rightarrow Cu\not=Cv$
+\end_inset
+
+.
+ Kromatično število
+\begin_inset Formula $\chi G$
+\end_inset
+
+ je najmanjši
+\begin_inset Formula $k$
+\end_inset
+
+, za katerega najdemo
+\begin_inset Formula $k-$
+\end_inset
+
+barvanje
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Za fiksen
+\begin_inset Formula $i$
+\end_inset
+
+ je
+\begin_inset Formula $\left\{ u\in VG;Cu=i\right\} $
+\end_inset
+
+ barvni razred, ki je neodvisna množica
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Za neodvisno množico
+\begin_inset Formula $S\subseteq VG$
+\end_inset
+
+ velja
+\begin_inset Formula $\forall u,v\in S:uv\not\in EG$
+\end_inset
+
+ ZDB je
+\begin_inset Quotes gld
+\end_inset
+
+brez povezav
+\begin_inset Quotes grd
+\end_inset
+
+.
+ Glej vprašanje
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "subsec:Kaj-je-neodvisnostno"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+.
+\end_layout
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\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
+
+,
+\begin_inset Formula $\chi P_{5,2}=3$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Definition*
+Klično število grafa
+\begin_inset Formula $G$
+\end_inset
+
+ označimo z
+\begin_inset Formula $\omega G$
+\end_inset
+
+.
+ Velja
+\begin_inset Formula $\omega G=\left|VH\right|$
+\end_inset
+
+, kjer je
+\begin_inset Formula $H$
+\end_inset
+
+ največji poln podgraf v
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Remark*
+\begin_inset Formula $\forall G\in\mathcal{G}:\chi G\geq\omega G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Definition*
+Požrešni algoritem barvanja: V poljubnem vrstnem redu zaporedno barvamo
+ vozlišča.
+ Posameznemu vozlišču priredimo najnižjo barvo, ki še ni uporabljena na
+ njegovih sosedih.
+\end_layout
+
+\begin_layout Fact*
+Vedno
+\begin_inset Formula $\exists$
+\end_inset
+
+ vrstni red barvanja, da požrešni algoritem vrne barvanje s
+\begin_inset Formula $\chi G$
+\end_inset
+
+ barvami.
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $\forall G\in\mathcal{G}:\chi G\leq\Delta G+1$
+\end_inset
+
+ ZDB
+\begin_inset Formula $\chi G$
+\end_inset
+
+ je kvečjemu 1 večji od največje stopnje v grafu.
+\end_layout
+
+\begin_layout Proof
+Naj bo
+\begin_inset Formula $x_{1},\dots,x_{n}$
+\end_inset
+
+ poljuben vrstni red vozlišč.
+ Poženemo požrešni algoritem.
+ Na poljubnem
+\begin_inset Formula $i$
+\end_inset
+
+tem koraku, ko barvamo
+\begin_inset Formula $x_{i}$
+\end_inset
+
+, je kvečjemu
+\begin_inset Formula $\deg_{G}x_{i}$
+\end_inset
+
+ barv, ki niso na razpolago, kar je
+\begin_inset Formula $\leq\Delta G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $G$
+\end_inset
+
+ ni regularen
+\begin_inset Formula $\Rightarrow\forall G\in\mathcal{G}:\chi G\leq\Delta G$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Naj bo
+\begin_inset Formula $x$
+\end_inset
+
+ tisto vozlišče, ki največje stopnje (*).
+ Vzamemo ga kot koren za BFS in z BFS vozlišča zmečemo v zaporedje
+\begin_inset Formula $a$
+\end_inset
+
+.
+ Nato požrešno barvamo v obratni smeri, kot jo določa
+\begin_inset Formula $a$
+\end_inset
+
+.
+ Na vsakem koraku, razen na korenu, bomo imeli soseda, ki še ni pobarvan,
+ torej je kvečjemu
+\begin_inset Formula $\deg_{G}x_{i}-1$
+\end_inset
+
+ barv, ki niso na razpolago, kar je
+\begin_inset Formula $\leq\Delta G$
+\end_inset
+
+.
+ Na zadnjem koraku (koren) pa po predpostavki (*) na razpolago ni kvečjemu
+
+\begin_inset Formula $\Delta G-1$
+\end_inset
+
+ barv.
+\end_layout
+
+\begin_layout Theorem*
+Brooks:
+\begin_inset Formula $G$
+\end_inset
+
+ povezan,
+\begin_inset Formula $G$
+\end_inset
+
+ niti poln niti lihi cikel
+\begin_inset Formula $\Rightarrow\chi G\leq\Delta G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Naj bo
+\begin_inset Formula $d_{1}\geq d_{2}\geq\cdots\geq d_{n}$
+\end_inset
+
+ zaporedje stopenj grafa
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Tedaj velja
+\begin_inset Formula $\chi G\leq1+\max_{i=1}^{n}\left(\min\left\{ d_{i},i-1\right\} \right)$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Poženimo požrešni algoritem barvanja v padajočem zaporedju stopenj.
+ Na
+\begin_inset Formula $i$
+\end_inset
+
+tem barvamo vozlišče stopnje
+\begin_inset Formula $d_{i}$
+\end_inset
+
+, zato imamo gotovo na voljo barvo iz
+\begin_inset Formula $\left\{ 1..d_{i}+1\right\} $
+\end_inset
+
+.
+ Ker smo doslej pobarvali zgolj
+\begin_inset Formula $i-1$
+\end_inset
+
+ vozlišč, imamo gotovo na voljo barvo iz
+\begin_inset Formula $\left\{ 1..i\right\} $
+\end_inset
+
+.
+ Algoritem pobarva vozlišče z barvo
+\begin_inset Formula $\leq\min\left\{ i,d_{i}+1\right\} $
+\end_inset
+
+.
+ Največja uporabljena barva
+\begin_inset Formula $k$
+\end_inset
+
+ je
+\begin_inset Formula $\leq\max_{i=1}^{n}\left\{ \min\left\{ d_{i}+1,i\right\} \right\} $
+\end_inset
+
+.
+ Torej
+\begin_inset Formula $\chi G\leq1+\max_{i=1}^{n}\left(\min\left\{ d_{i},i-1\right\} \right)$
+\end_inset
+
+ (izven
+\begin_inset Formula $\max$
+\end_inset
+
+ smo prišteli 1, znotraj
+\begin_inset Formula $\min$
+\end_inset
+
+ smo od vseh elementov 1 odšteli).
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+TODO XXX FIXME dokaz in trditev za barvanje ravninskega grafa s petimi barvami
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+Kaj je kromatični indeks
+\begin_inset Formula $\chi'\left(G\right)$
+\end_inset
+
+ grafa
+\begin_inset Formula $G$
+\end_inset
+
+? Kaj pravi Vizingov izrek in kako na njegovi osnovi razdelimo vse grafe
+ v dva razreda?
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $k-$
+\end_inset
+
+barvanje povezav je preslikava
+\begin_inset Formula $C:EG\to\left\{ 1..k\right\} \ni:uv,uw\in EG\Rightarrow C\left(uv\right)\not=C\left(uw\right)$
+\end_inset
+
+.
+ ZDB povezavi s skupnim krajiščem dobita različni barvi.
+ Kromatični indeks grafa
+\begin_inset Formula $G$
+\end_inset
+
+ (oznaka
+\begin_inset Formula $\chi'G$
+\end_inset
+
+) je najmanjši
+\begin_inset Formula $k$
+\end_inset
+
+, za katerega
+\begin_inset Formula $\exists k-$
+\end_inset
+
+barvanje grafa
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\chi'C_{n}=\begin{cases}
+2 & ;n\text{ sod}\\
+3 & ;n\text{ lih}
+\end{cases}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Vizing:
+\begin_inset Formula $\forall G\in\mathcal{G}:\Delta G\leq\chi'G\leq\Delta G+1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Prvi neenačaj je očiten, drugega ne bomo dokazali.
+\end_layout
+
+\begin_layout Definition*
+Graf
+\begin_inset Formula $G$
+\end_inset
+
+ je razreda I, če je
+\begin_inset Formula $\chi'G=\Delta G$
+\end_inset
+
+ oziroma razreda II, če je
+\begin_inset Formula $\chi'G=\Delta G+1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $C_{2n}$
+\end_inset
+
+ so razreda
+\begin_inset Formula $I$
+\end_inset
+
+,
+\begin_inset Formula $C_{2n+1}$
+\end_inset
+
+ so razreda II,
+\begin_inset Formula $K_{3}$
+\end_inset
+
+ je razreda II,
+\begin_inset Formula $K_{4}$
+\end_inset
+
+ je razreda
+\begin_inset Formula $I$
+\end_inset
+
+
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+TODO XXX FIXME dokaz, da so dvodelni grafi I, K_2k razreda I in K_2k+1 razreda
+ II.
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+\begin_inset CommandInset label
+LatexCommand label
+name "subsec:Kaj-je-neodvisnostno"
+
+\end_inset
+
+Kaj je neodvisnostno število grafa? Zanj podajte spodnjo mejo in zgornjo
+ mejo.
+ Opišite algoritem za izračun neodvisnostnega števila drevesa.
+\end_layout
+
+\begin_layout Definition*
+Če je
+\begin_inset Formula $G$
+\end_inset
+
+ graf in
+\begin_inset Formula $I\subseteq VG$
+\end_inset
+
+, je
+\begin_inset Formula $I$
+\end_inset
+
+ neodvisna
+\begin_inset Formula $\Leftrightarrow\forall u,v\in I:uv\not\in EG$
+\end_inset
+
+ ZDB če nobeni dve vozlišči v I nista sosednji v
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Moč največje neodvisne množice v
+\begin_inset Formula $G$
+\end_inset
+
+ je neodvisnostno število
+\begin_inset Formula $G$
+\end_inset
+
+, označeno z
+\begin_inset Formula $\alpha G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\alpha K_{n}=1$
+\end_inset
+
+,
+\begin_inset Formula $\alpha C_{n}=\lfloor\frac{n}{2}\rfloor$
+\end_inset
+
+,
+\begin_inset Formula $\alpha P_{5,2}=4$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $\forall G\in\mathcal{G}:\alpha G\cdot\chi G\geq\left|VG\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+Naj bo
+\begin_inset Formula $\chi G=k$
+\end_inset
+
+ in
+\begin_inset Formula $V_{1},\dots,V_{k}$
+\end_inset
+
+ barvni razredi nekega fiksnega barvanja s k barvami.
+ Slednji so neodvisne množice.
+
+\begin_inset Formula $\forall i\in\left\{ 1..k\right\} :\left|V_{i}\right|\leq\alpha G\Rightarrow\left|VG\right|=\sum_{i=1}^{k}\left|V_{i}\right|\leq\sum_{i=1}^{k}\alpha G=\alpha G\cdot k=\alpha G\chi G$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Corollary*
+Spodnja meja za neodvisnostno število
+\begin_inset Formula $\alpha G\geq\frac{\left|VG\right|}{\chi G}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Claim*
+Zgornja meja za neodvisnostno število:
+\begin_inset Formula $\alpha G\leq\left|VG\right|-\frac{\left|EG\right|}{\Delta G}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Naj bo
+\begin_inset Formula $I$
+\end_inset
+
+ poljubna največja neodvisna množica v
+\begin_inset Formula $G$
+\end_inset
+
+, torej
+\begin_inset Formula $\left|I\right|=\alpha G$
+\end_inset
+
+.
+ V
+\begin_inset Formula $VG\setminus I$
+\end_inset
+
+ je vozlišč
+\begin_inset Formula $\left|VG\right|-\alpha G$
+\end_inset
+
+.
+ Ker vozlišča v
+\begin_inset Formula $I$
+\end_inset
+
+ medsebojno niso povezana,
+\begin_inset Formula $\left|EG\right|\leq\left(\left|VG\right|-\alpha G\right)\cdot\Delta G\Rightarrow\left|EG\right|\leq\left|VG\right|\Delta G-\alpha G\Delta G\Rightarrow\alpha G\Delta G\leq\left|VG\right|\Delta G-\left|EG\right|\Rightarrow\alpha G\leq\left|VG\right|-\frac{\left|EG\right|}{\Delta G}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $Q_{d},d\geq1$
+\end_inset
+
+: Zgornja meja:
+\begin_inset Formula $\alpha Q_{d}\leq\left|VQ_{d}\right|-\frac{\left|EQ_{d}\right|}{\Delta Q_{d}}=2^{d}-\frac{d2^{d-1}}{d}=2^{d}-2^{d-1}=2^{d-1}$
+\end_inset
+
+, Spodnja meja:
+\begin_inset Formula $\alpha Q_{d}\geq\frac{\left|VQ_{d}\right|}{\chi Q_{d}}=\frac{2^{d}}{2}=2^{d-1}$
+\end_inset
+
+, torej
+\begin_inset Formula $\alpha Q_{d}=2^{d-1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Paragraph*
+Neodvisnostno število dreves
+\end_layout
+
+\begin_layout Standard
+Naj bo
+\begin_inset Formula $T$
+\end_inset
+
+ drevo s poljubnim korenom
+\begin_inset Formula $r\in VT$
+\end_inset
+
+.
+ Odslej na drevo glejmo
+\begin_inset Formula $T$
+\end_inset
+
+ kot na drevo s korenom
+\begin_inset Formula $r$
+\end_inset
+
+.
+ Za neodvisno množico
+\begin_inset Formula $S$
+\end_inset
+
+ drevesa
+\begin_inset Formula $T$
+\end_inset
+
+ in poljubno vozlišče
+\begin_inset Formula $x\in VT$
+\end_inset
+
+ velja:
+\begin_inset Formula $x\in S\Rightarrow$
+\end_inset
+
+ potomci (otroci)
+\begin_inset Formula $x\not\in S$
+\end_inset
+
+.
+ Če pa
+\begin_inset Formula $x\not\in S$
+\end_inset
+
+, pa
+\begin_inset Formula $S$
+\end_inset
+
+ sme vsebovati potomce
+\begin_inset Formula $x$
+\end_inset
+
+.
+ Z
+\begin_inset Formula $Iv$
+\end_inset
+
+ označimo velikost največje neodvisne množice s korenom v
+\begin_inset Formula $v\in VT$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+Očitno velja
+\begin_inset Formula $\alpha T=Ir$
+\end_inset
+
+.
+ Z rekurzivnim postopkom določimo
+\begin_inset Formula $\text{\ensuremath{\alpha T}}$
+\end_inset
+
+ na tak način:
+\begin_inset Formula
+\[
+\alpha T=Ir=\text{\ensuremath{\max}\left\{ 1+\sum_{v\in\text{vnuki/drugi potomci \ensuremath{r}}}Iv,\sum_{v\in\text{otroci/potomci }r}Iv\right\} }
+\]
+
+\end_inset
+
+Formula je očitna.
+ Na vsakem rekurzivnem koraku lahko bodisi v množico izberemo
+\begin_inset Formula $v$
+\end_inset
+
+ in ne izberemo njegovih potomcev, bodisi izberemo potomce, njega pa ne.
+ Z rekurzivnim algoritmom preverimo vse možnosti.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\alpha T_{n}$
+\end_inset
+
+, kjer je
+\begin_inset Formula $T_{n}$
+\end_inset
+
+ polno dvojiško drevo globine
+\begin_inset Formula $n\in\mathbb{N}_{0}$
+\end_inset
+
+: Vpeljimo zaporedje
+\begin_inset Formula $a_{n}=\alpha T_{n}$
+\end_inset
+
+ in velja:
+\begin_inset Formula $\left(a_{n}\right)_{n\in\mathbb{N}_{0}}=\left[1,2,5,10,21,42,\dots\right]$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Theorem*
+\begin_inset Formula $a_{0}=1$
+\end_inset
+
+,
+\begin_inset Formula $a_{1}=2$
+\end_inset
+
+, za
+\begin_inset Formula $n\geq2$
+\end_inset
+
+:
+\begin_inset Formula $a_{n}=\begin{cases}
+2_{n-1}+1 & ;n\text{ sod}\\
+2_{n-1} & ;n\text{ lih}
+\end{cases}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Z indukcijo.
+ Baza sta
+\begin_inset Formula $a_{0}$
+\end_inset
+
+ in
+\begin_inset Formula $a_{1}$
+\end_inset
+
+.
+ Indukcijska predpostavka je dana v izreku.
+ ITD DOPIŠI DOKAZ.
+
+\begin_inset Quotes gld
+\end_inset
+
+DS2P FMF 2024-04-18
+\begin_inset Quotes grd
+\end_inset
+
+ stran 5.
+\end_layout
+
+\begin_layout Subsection
+\begin_inset CommandInset label
+LatexCommand label
+name "subsec:Kaj-je-dominacijsko"
+
+\end_inset
+
+Kaj je dominacijsko število grafa? Zanj podajte spodnjo mejo in zgornjo
+ mejo.
+ Kakšna je zveza med dominacijskim številom grafa in njegovega vpetega podgrafa?
+\end_layout
+
+\begin_layout Standard
+Naj bo
+\begin_inset Formula $G$
+\end_inset
+
+ graf.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Neodvisna množica
+\begin_inset Formula $G$
+\end_inset
+
+ je maksimalna, če ni prava podmnožica kakšne neodvisne množice v
+\begin_inset Formula $G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+\begin_inset Formula $N_{G}\left(u\right)\coloneqq\left\{ v;uv\in EG\right\} $
+\end_inset
+
+ je soseščina vozlišča
+\begin_inset Formula $u$
+\end_inset
+
+ (sosedje
+\begin_inset Formula $u$
+\end_inset
+
+ v
+\begin_inset Formula $G$
+\end_inset
+
+).
+
+\begin_inset Formula $N_{G}\left[u\right]\coloneqq N_{G}\left(u\right)\cup\left\{ u\right\} $
+\end_inset
+
+ je zaprta soseščina vozlišča
+\begin_inset Formula $u$
+\end_inset
+
+.
+
+\begin_inset Formula $N_{G}\left[D\right]=\bigcup_{u\in D}N_{G}\left[u\right]$
+\end_inset
+
+ je zaprta soseščina množice vozlišč
+\begin_inset Formula $D.$
+\end_inset
+
+
+\begin_inset Formula $D\subseteq VG$
+\end_inset
+
+ dominira
+\begin_inset Formula $X\subseteq VG\Leftrightarrow X\subseteq N_{G}\left[D\right]$
+\end_inset
+
+.
+ Če
+\begin_inset Formula $D$
+\end_inset
+
+ dominira
+\begin_inset Formula $VG$
+\end_inset
+
+, pravimo, da je
+\begin_inset Formula $D$
+\end_inset
+
+ dominantna množica grafa
+\begin_inset Formula $G$
+\end_inset
+
+.
+ ZDB
+\begin_inset Formula $D$
+\end_inset
+
+ dominantna množica
+\begin_inset Formula $G\Leftrightarrow\forall u\in VG:u\in D\vee\exists x\in D\ni:xu\in EG$
+\end_inset
+
+ ZDB vsako vozlišče je v
+\begin_inset Formula $D$
+\end_inset
+
+ ali pa ima soseda iz
+\begin_inset Formula $D$
+\end_inset
+
+.
+ Moč najmanjše dominacijske množice za
+\begin_inset Formula $G$
+\end_inset
+
+ je dominacijsko število grafa
+\begin_inset Formula $G$
+\end_inset
+
+, označeno z
+\begin_inset Formula $\gamma G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Remark*
+Vsaka maksimalna neodvisna množica grafa je njegova dominantna množica.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\gamma K_{n}=1$
+\end_inset
+
+,
+\begin_inset Formula $\gamma C_{n}=\lceil\frac{n}{3}\rceil$
+\end_inset
+
+,
+\begin_inset Formula $\gamma P_{5,2}=3$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Theorem*
+Za vsak graf brez izoliranih vozlišč velja, da je
+\begin_inset Formula $\lceil\frac{\left|VG\right|}{\Delta G+1}\rceil\leq\gamma G\leq\lfloor\frac{\left|VG\right|}{2}\rfloor$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Spodnja meja: Če je
+\begin_inset Formula $G$
+\end_inset
+
+ dominantna množica in
+\begin_inset Formula $u\in D$
+\end_inset
+
+, potem
+\begin_inset Formula $u$
+\end_inset
+
+ dominira
+\begin_inset Formula $\leq\deg_{G}u+1$
+\end_inset
+
+ vozlišč, torej vsako vozlišče iz
+\begin_inset Formula $D$
+\end_inset
+
+ dominira kvečjemu
+\begin_inset Formula $\Delta G+1$
+\end_inset
+
+ vozlišč.
+ Ker
+\begin_inset Formula $VG\subseteq N_{G}\left[D\right]$
+\end_inset
+
+ (unija zaprtih okolic vozlišč iz dominantne množice prekrije cel graf),
+ je
+\begin_inset Formula $\left|D\right|\geq\frac{\left|VG\right|}{\Delta G+1}$
+\end_inset
+
+, kajti
+\begin_inset Formula $\left|VG\right|=\left|N_{G}\left[D\right]\right|=\left|\bigcup_{u\in D}N_{G}\left[u\right]\right|\leq\sum_{u\in D}N\left(u\right)\leq\sum_{u\in D}$
+\end_inset
+
+
+\begin_inset Formula $\left(\Delta G+1\right)=\gamma G\left(\Delta G+1\right)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Zgornja meja: Naj bo
+\begin_inset Formula $I$
+\end_inset
+
+ poljubna maksimalna neodvisna množica.
+ Vemo, da je
+\begin_inset Formula $I$
+\end_inset
+
+ tedaj dominantna.
+ Če je
+\begin_inset Formula $\left|I\right|\leq\frac{\left|VG\right|}{2}$
+\end_inset
+
+ smo dokazali, sicer vzemimo njen komplement
+\begin_inset Formula $I'\coloneqq VG\setminus I$
+\end_inset
+
+.
+ Trdimo, da je
+\begin_inset Formula $I'$
+\end_inset
+
+ dominantna.
+ Vzemimo poljubno
+\begin_inset Formula $u\in G$
+\end_inset
+
+.
+ Če
+\begin_inset Formula $u\in I'$
+\end_inset
+
+, dominira samega sebe, sicer, ker je
+\begin_inset Formula $G$
+\end_inset
+
+ brez izoliranih vozlišč, ima
+\begin_inset Formula $u$
+\end_inset
+
+ vsaj enega soseda, ker pa je
+\begin_inset Formula $I$
+\end_inset
+
+ neodvisna, je ta sosed v
+\begin_inset Formula $I'$
+\end_inset
+
+, torej je
+\begin_inset Formula $I'$
+\end_inset
+
+ dominantna in ima
+\begin_inset Formula $\leq\frac{\left|VG\right|}{2}$
+\end_inset
+
+ vozlišč in velja
+\begin_inset Formula $\gamma G\leq\min\left\{ \left|I\right|,\left|I'\right|\right\} \leq\frac{\left|VG\right|}{2}$
+\end_inset
+
+, kajti
+\begin_inset Formula $I\cup I'=VG$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+Enakost spodnje meje velja v
+\begin_inset Formula $K_{n}$
+\end_inset
+
+,
+\begin_inset Formula $C_{n}$
+\end_inset
+
+.
+ Enakost zgornje meje velja pri glavnikih
+\begin_inset Formula $T_{n}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+dodaj 2-pakiranje in 2-pakirno število
+\begin_inset Formula $\rho$
+\end_inset
+
+!
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Če je
+\begin_inset Formula $H$
+\end_inset
+
+ vpet podgraf
+\begin_inset Formula $G$
+\end_inset
+
+, je
+\begin_inset Formula $\gamma G\leq\gamma H$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Naj bo
+\begin_inset Formula $D$
+\end_inset
+
+ minimalna dominantna množica za
+\begin_inset Formula $H$
+\end_inset
+
+.
+
+\begin_inset Formula $\left|D\right|=\gamma H$
+\end_inset
+
+.
+ Tedaj je
+\begin_inset Formula $D$
+\end_inset
+
+ očitno tudi dominantna množica za
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Toda seveda se lahko zgodi, da je v
+\begin_inset Formula $G$
+\end_inset
+
+ moč najti manjšo dominantno množico kot v
+\begin_inset Formula $H$
+\end_inset
+
+, ker ima
+\begin_inset Formula $G$
+\end_inset
+
+ lahko dodatne povezave.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+TODO XXX FIXME vpeto drevo in
+\begin_inset Formula $\gamma$
+\end_inset
+
+
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+Kaj je dominacijsko število grafa in kaj je celotno dominacijsko število
+ grafa? Kakšna je zveza med njima? Kakšna je povezava med dominacijskim
+ številom grafa in kromatičnim številom komplementa?
+\end_layout
+
+\begin_layout Standard
+Dominacijsko število grafa je definirano v vprašanju
+\begin_inset CommandInset ref
+LatexCommand ref
+reference "subsec:Kaj-je-dominacijsko"
+plural "false"
+caps "false"
+noprefix "false"
+
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Definition*
+Dominantna množica
+\begin_inset Formula $D$
+\end_inset
+
+ grafa
+\begin_inset Formula $G$
+\end_inset
+
+ je povezana, če inducira povezan podgraf, neodvisna, če inducira podgraf
+ brez povezav in
+\series bold
+celotna
+\series default
+, če ima vsako vozlišče iz
+\begin_inset Formula $VG$
+\end_inset
+
+ soseda v
+\begin_inset Formula $D$
+\end_inset
+
+ (tudi vozlišča iz
+\begin_inset Formula $D$
+\end_inset
+
+).
+ Velikost najmanjše povezane dominantne množice označimo z
+\begin_inset Formula $\gamma_{c}G$
+\end_inset
+
+, neodvisne z
+\begin_inset Formula $\gamma_{i}G$
+\end_inset
+
+ in
+\series bold
+celotne
+\series default
+ z
+\begin_inset Formula $\gamma_{t}G$
+\end_inset
+
+ (connected, independent in total).
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\gamma_{t}K_{n}=2$
+\end_inset
+
+,
+\begin_inset Formula $\gamma_{t}P_{n}=\lfloor\frac{n}{2}\rfloor+\lceil\frac{n}{2}\rceil-\lfloor\frac{n}{4}\rfloor$
+\end_inset
+
+ (gledamo parčke, ki se dominirajo).
+\end_layout
+
+\begin_layout Theorem*
+Za vsak graf brez izoliranih vozlišč velja
+\begin_inset Formula $\gamma G\leq\gamma_{t}G\leq2\gamma G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Spodnja meja je očitna, kajti biti celotna dominantna množica je strožji
+ pogoj kot biti dominantna množica.
+ Dokažimo
+\begin_inset Formula $\gamma_{t}G\leq2\gamma G$
+\end_inset
+
+: Naj bo
+\begin_inset Formula $D$
+\end_inset
+
+ poljubna dominantna množica
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Vsakemu
+\begin_inset Formula $x\in D$
+\end_inset
+
+ priredimo nekega soseda od
+\begin_inset Formula $x$
+\end_inset
+
+, recimo
+\begin_inset Formula $x'$
+\end_inset
+
+ in ga dodajmo v
+\begin_inset Formula $\hat{D}$
+\end_inset
+
+, torej
+\begin_inset Formula $\hat{D}=D\cup\left\{ x';x\in D\right\} $
+\end_inset
+
+, s čimer dominantno množico spremenimo v celotno tako, da ji kvečjemu podvojimo
+ število vozlišč.
+\end_layout
+
+\begin_layout Example*
+Enakost spodnje meje se pojavi pri
+\begin_inset Formula $\gamma C_{4}=\gamma_{t}C_{4}=2$
+\end_inset
+
+, neenakost pa pri recimo
+\begin_inset Formula $\gamma G_{3}=2\not=4=\gamma_{t}Q_{3}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsection
+Kaj je grupoid, polgrupa, monoid, grupa? Kako v monoidu izračunamo inverz
+ produkta obrnljivih elementov? Kako definiramo potence v monoidu in kateri
+ računski zakoni veljajo zanje?
+\end_layout
+
+\begin_layout Definition*
+Če uvedemo binarno operacijo
+\begin_inset Formula $f$
+\end_inset
+
+ na množici
+\begin_inset Formula $A$
+\end_inset
+
+ takole:
+\begin_inset Formula $f:A\times A\to A,f$
+\end_inset
+
+ preslikava, je par
+\begin_inset Formula $\left(A,f\right)$
+\end_inset
+
+
+\series bold
+grupoid
+\series default
+.
+ ZDB zahtevamo, da je operacija preslikava (domena je enaka definicijskemu
+ območju) in s tem zaprtost operacije.
+ Dvojiški operator
+\begin_inset Formula $f\left(a,b\right)$
+\end_inset
+
+ pišimo kot
+\begin_inset Formula $a\cdot b$
+\end_inset
+
+.
+
+\end_layout
+
+\begin_layout Definition*
+Če
+\begin_inset Formula $\forall a,b,c\in A:\left(a\cdot b\right)\cdot c=a\cdot\left(b\cdot c\right)$
+\end_inset
+
+ (asociativnost), pravimo, da je
+\begin_inset Formula $\left(A,\cdot\right)$
+\end_inset
+
+
+\series bold
+podgrupa
+\series default
+ ZDB asocietiven grupoid.
+\end_layout
+
+\begin_layout Definition*
+Enota je element
+\begin_inset Formula $e\in A\ni:\forall a\in A:a\cdot e=e\cdot a=a$
+\end_inset
+
+.
+ Polgrupi z enoto pravimo
+\series bold
+monoid
+\series default
+.
+
+\end_layout
+
+\begin_layout Definition*
+Monoidu, v katerem so vsi elementi obrnljivi, pravimo
+\series bold
+grupa
+\series default
+ ZDB
+\series bold
+
+\begin_inset Formula $\forall a\in A\exists b\in A\ni:a\cdot b=b\cdot a=e$
+\end_inset
+
+
+\series default
+.
+\end_layout
+
+\begin_layout Remark*
+Ker so inverzi v monoidu enolični (dokaz pri LA), inverz
+\begin_inset Formula $a$
+\end_inset
+
+ označimo z
+\begin_inset Formula $a^{-1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\left(\mathcal{G},\square\right)$
+\end_inset
+
+ monoid,
+\begin_inset Formula $\left(\mathbb{R}_{0}^{+}=\left\{ x\in\mathbb{R};x\geq0\right\} ,\max\right)$
+\end_inset
+
+ monoid, množica vseh nizov/seznamov s concat operacijo je monoid.
+\end_layout
+
+\begin_layout Theorem*
+Če sta
+\begin_inset Formula $a$
+\end_inset
+
+ in
+\begin_inset Formula $b$
+\end_inset
+
+ v monoidu obrnljiva, je obrnljiv tudi njun produkt in velja
+\begin_inset Formula $\left(a\cdot b\right)^{-1}=b^{-1}\cdot a^{-1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+\begin_inset Formula $\left(a\cdot b\right)\cdot\left(b^{-1}\cdot a^{-1}\right)=a\cdot\left(b\cdot b^{-1}\right)\cdot a^{-1}=a\cdot e\cdot a^{-1}=a\cdot a^{-1}=e$
+\end_inset
+
+ in podobno
+\begin_inset Formula $\left(b^{-1}a^{-1}\right)\left(ab\right)=e$
+\end_inset
+
+, torej
+\begin_inset Formula $\left(b^{-1}a^{-1}\right)\left(ab\right)=\left(ab\right)\left(b^{-1}a^{-1}\right)=e\Rightarrow ab=\left(b^{-1}a^{-1}\right)$
+\end_inset
+
+ po definiciji inverza.
+\end_layout
+
+\begin_layout Corollary*
+Če so
+\begin_inset Formula $a_{1},\dots,a_{k}$
+\end_inset
+
+ obrnljivi elementi monoida, je
+\begin_inset Formula $\left(a_{1}\cdots a_{k}\right)$
+\end_inset
+
+ obrnljiv element monoida in velja
+\begin_inset Formula $\left(a_{1}\cdots a_{k}\right)^{-1}=a_{k}^{-1}\cdots a_{1}^{-1}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Dokaz z indukcijo: Baza:
+\begin_inset Formula $k=2$
+\end_inset
+
+ velja, Korak: predpostavimo
+\begin_inset Formula $\left(a_{1}\cdots a_{k}\right)^{-1}=a_{k}^{-1}\cdots a_{1}^{-1}$
+\end_inset
+
+.
+ Množimo z desne z
+\begin_inset Formula $a_{k+1}$
+\end_inset
+
+ in smo dokazali.
+\end_layout
+
+\begin_layout Definition*
+Naj bo
+\begin_inset Formula $\left(A,\cdot\right)$
+\end_inset
+
+ monoid,
+\begin_inset Formula $n\in\mathbb{N}_{0}$
+\end_inset
+
+.
+
+\begin_inset Formula $a^{0}\coloneqq e$
+\end_inset
+
+,
+\begin_inset Formula $a^{n}=a\cdot a^{n-1}$
+\end_inset
+
+ za
+\begin_inset Formula $n\geq1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Corollary*
+Velja torej
+\begin_inset Formula $a^{n}a^{m}=a^{n+m}$
+\end_inset
+
+,
+\begin_inset Formula $\left(a^{n}\right)^{m}=a^{nm}$
+\end_inset
+
+,
+\begin_inset Formula $\left(a^{-1}\right)^{n}=a^{-1}\cdots n-\text{krat}\cdots a^{-1}=\left(a\cdots n-\text{krat}\cdots a\right)^{-1}=\left(a^{n}\right)^{-1}$
+\end_inset
+
+.
+ Torej za obrnljiv
+\begin_inset Formula $a$
+\end_inset
+
+ velja
+\begin_inset Formula $\left(a^{n}\right)^{-1}=\left(a^{-1}\right)^{n}$
+\end_inset
+
+.
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+dodaj podgrupe etc
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Subsection
+Kaj je red elementa v grupi? Kaj je pravilo krajšanja v grupi? Dokažite
+ ga.
+ Kako se pravilo krajšanja odraža v Cayleyevi tabeli grupe?
+\end_layout
+
+\begin_layout Definition*
+Cayleyeva tabela za grupoid
+\begin_inset Formula $\left(A,\cdot\right)$
+\end_inset
+
+ je kvadratna tabela širine
+\begin_inset Formula $\left|A\right|$
+\end_inset
+
+, kjer ima
+\begin_inset Formula $i,j-$
+\end_inset
+
+ta celica vrednost
+\begin_inset Formula $a_{i}\cdot a_{j}$
+\end_inset
+
+, kjer je
+\begin_inset Formula $a_{k}$
+\end_inset
+
+
+\begin_inset Formula $k-$
+\end_inset
+
+ti element množice
+\begin_inset Formula $A$
+\end_inset
+
+.
+ Pač izberemo si neko linearno urejenost
+\begin_inset Formula $A$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Naj bo
+\begin_inset Formula $\left(G,\cdot\right)$
+\end_inset
+
+ končna grupa in
+\begin_inset Formula $a\in G$
+\end_inset
+
+.
+ Tedaj je red elementa
+\begin_inset Formula $a$
+\end_inset
+
+ najmanjši
+\begin_inset Formula $n\in\mathbb{N}\ni:a^{n}=e$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Theorem*
+Dirichletovo načelo:
+\begin_inset Formula $\exists n,m\in\left[k+1\right],n\not=m:a^{n}=a^{m}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Proof
+BSŠ
+\begin_inset Formula $n<m$
+\end_inset
+
+.
+
+\begin_inset Formula $a^{n}=a^{m}\Rightarrow a^{n}\left(a^{m}\right)^{-1}=a^{m}\left(a^{m}\right)^{-1}\Rightarrow a^{n-m}=e$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Pravilo krajšanja: Če je
+\begin_inset Formula $G$
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+Ko omenimo algebrajsko strukturo, občasno omenimo le množico, ko je iz konteksta
+ operacija implicitno znana.
+\end_layout
+
+\end_inset
+
+ grupa,
+\begin_inset Formula $a,b,c\in G$
+\end_inset
+
+, velja
+\begin_inset Formula $ab=ac\Rightarrow b=c$
+\end_inset
+
+ in
+\begin_inset Formula $ba=ca\Rightarrow b=c$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Množimo obe strani z leve ali desne z inverzom
+\begin_inset Formula $a$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Corollary*
+V Cayleyevi tabeli grupe se v vsaki vrstici in v vsakem stolpcu pojavijo
+ vsi elementi grupe.
+\end_layout
+
+\begin_layout Subsection
+Kaj je permutacijska grupa? Kaj je simetrična grupa
+\begin_inset Formula $S_{n}$
+\end_inset
+
+ in kaj je alternirajoča grupa
+\begin_inset Formula $A_{n}$
+\end_inset
+
+? Kaj pravi Cayleyev izrek (o univerzalnosti permutacijskih grup) in kakšna
+ je ideja njegovega dokaza?
+\end_layout
+
+\begin_layout Definition*
+Naj bo
+\begin_inset Formula $A$
+\end_inset
+
+ množica.
+ Permutacija
+\begin_inset Formula $A$
+\end_inset
+
+ je bijekcija
+\begin_inset Formula $A\to A$
+\end_inset
+
+.
+ Permutacijska grupa je množica nekaj permutacij
+\begin_inset Formula $A$
+\end_inset
+
+, ki ga komponiranje tvorijo grupo.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Simetrična grupa:
+\begin_inset Formula $S_{n}\coloneqq\left\{ \pi;\pi:\left\{ 1..n\right\} \to\left\{ 1..n\right\} \text{ bijekcija}\right\} $
+\end_inset
+
+.
+ Alternirajoča grupa:
+\begin_inset Formula $A_{n}\coloneqq\left\{ \pi\in S_{n};\pi\text{ soda}\right\} $
+\end_inset
+
+.
+ Permutacija je soda, če je v zapisu z disjunktnimi cikli vsota dolžin ciklov,
+ ki ji odštejemo število ciklov, soda.
+\end_layout
+
+\begin_layout Theorem*
+\begin_inset Formula $\left|A_{n}\right|=\frac{n!}{2}$
+\end_inset
+
+.
+
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+DOKAŽI TODO XXX FIXME
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Naj bosta
+\begin_inset Formula $\left(G,\circ\right)$
+\end_inset
+
+ in
+\begin_inset Formula $\left(H,*\right)$
+\end_inset
+
+ grupi.
+
+\begin_inset Formula $f:G\to H$
+\end_inset
+
+ je hm
+\begin_inset Formula $\varphi\Leftrightarrow\forall x,y\in G:f\left(x\circ y\right)=fx*fy$
+\end_inset
+
+.
+ Če je
+\begin_inset Formula $f$
+\end_inset
+
+ tudi bijekcija, je
+\begin_inset Formula $f:G\to H$
+\end_inset
+
+ izomorfizem.
+ Grupi sta izomorfni, če obstaja izomorfizem med njima.
+ Tedaj pišemo
+\begin_inset Formula $G\approx H$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Theorem*
+Cayley: Vsaka grupa je izomorfna neki permutacijski grupi.
+\end_layout
+
+\begin_layout Proof
+(skica dokaza) Naj bo
+\begin_inset Formula $\left(G,\cdot\right)$
+\end_inset
+
+ grupa.
+ Vsakemu elementu grupe priredimo preslikavo
+\begin_inset Formula $g\in G\mapsto\alpha_{g}:G\to G$
+\end_inset
+
+, ki slika takole:
+\begin_inset Formula $\forall x\in G:\alpha_{k}x=g\cdot x$
+\end_inset
+
+.
+
+\begin_inset Formula $\alpha_{g}$
+\end_inset
+
+ je permutacija
+\begin_inset Formula $G$
+\end_inset
+
+, saj je bijektivna, ker velja pravilo krajšanja:
+\begin_inset Formula $x\not=y\Rightarrow\alpha_{g}x\overset{\text{pravilo krajšanja}}{=}gx\not=gy=\alpha_{g}y$
+\end_inset
+
+.
+
+\begin_inset Formula $\left\{ \alpha_{g};\forall g\in G\right\} $
+\end_inset
+
+ tvori permutacijsko grupo, ki je izomorfna izvorni grupi:
+\begin_inset Formula $\left(\left\{ \alpha_{g};\forall g\in G\right\} ,\circ\right)\approx\left(G,\cdot\right)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsection
+Kaj so odseki grupe
+\begin_inset Formula $G$
+\end_inset
+
+ po podgrupi
+\begin_inset Formula $H$
+\end_inset
+
+? Kdaj je
+\begin_inset Formula $aH=H$
+\end_inset
+
+ in kdaj je
+\begin_inset Formula $aH=Ha$
+\end_inset
+
+? Kaj je vsebina Lagrangeovega izreka o moči podgrup in končnih grup?
+\end_layout
+
+\begin_layout Definition*
+Naj bo
+\begin_inset Formula $\left(G,\cdot\right)$
+\end_inset
+
+ grupa in
+\begin_inset Formula $H$
+\end_inset
+
+ podgrupa
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+prosim definiraj podgrupo
+\end_layout
+
+\end_inset
+
+
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Če je
+\begin_inset Formula $a\in G$
+\end_inset
+
+, definiramo
+\begin_inset Formula $aH=\left\{ ah,h\in H\right\} $
+\end_inset
+
+ (desni odsek podgrupe
+\begin_inset Formula $H$
+\end_inset
+
+) in
+\begin_inset Formula $Ha=\left\{ ha,h\in H\right\} $
+\end_inset
+
+ (levi odsek podgrupe
+\begin_inset Formula $H$
+\end_inset
+
+).
+\end_layout
+
+\begin_layout Theorem*
+Naj bo
+\begin_inset Formula $G$
+\end_inset
+
+ grupa in
+\begin_inset Formula $a,b\in G$
+\end_inset
+
+ in
+\begin_inset Formula $H$
+\end_inset
+
+ podgrupa
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Tedaj veljajo naslednje lastnosti:
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:"
+
+\end_inset
+
+
+\begin_inset Formula $a\in aH$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:-1"
+
+\end_inset
+
+
+\begin_inset Formula $aH=H\Leftrightarrow a\in H$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $aH=bH\nabla aH\cap bH=\emptyset$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $aH=bH\Leftrightarrow a^{-1}b\in H$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $\left|aH\right|=\left|bH\right|$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset CommandInset label
+LatexCommand label
+name "enu:-2"
+
+\end_inset
+
+
+\begin_inset Formula $aH=Ha\Leftrightarrow H=aHa^{-1}$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $aH$
+\end_inset
+
+ podgrupa
+\begin_inset Formula $G\Leftrightarrow a\in H$
+\end_inset
+
+
+\end_layout
+
+\end_deeper
+\begin_layout Proof
+Dokažimo trditve:
+\end_layout
+
+\begin_deeper
+\begin_layout Enumerate
+\begin_inset Formula $e\in H\Rightarrow a\cdot e=a\in aH$
+\end_inset
+
+
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $\left(\Rightarrow\right)$
+\end_inset
+
+
+\begin_inset Formula $a\overset{\ref{enu:}}{\in}aH=H\Rightarrow a\in H$
+\end_inset
+
+,
+\begin_inset Formula $\left(\Leftarrow\right)$
+\end_inset
+
+ Najprej ena vsebovanost:
+\begin_inset Formula $\forall x\in aH\exists h\in H\ni:x=ah$
+\end_inset
+
+, ker
+\begin_inset Formula $a\in H$
+\end_inset
+
+, je po zaprtosti podgrupe
+\begin_inset Formula $H$
+\end_inset
+
+
+\begin_inset Formula $ah=x\in H\Rightarrow aH\subseteq H$
+\end_inset
+
+.
+ Nato še druga vsebovanost:
+\begin_inset Formula $\forall x\in H:a^{-1}x\in H\Rightarrow a\left(a^{-1}x\right)=x\in aH\Rightarrow H\subseteq aH$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+Imejmo
+\begin_inset Formula $aH$
+\end_inset
+
+,
+\begin_inset Formula $bH$
+\end_inset
+
+.
+ Če je
+\begin_inset Formula $aH=bH$
+\end_inset
+
+, smo dokazali, sicer
+\begin_inset Formula $\exists x\in aH\cup bH$
+\end_inset
+
+.
+ Ker
+\begin_inset Formula $x\in aH\Rightarrow\exists h'\in H\ni:x=ah'$
+\end_inset
+
+.
+ Ker
+\begin_inset Formula $x\in bH\exists h''\in H\ni:x=bh''$
+\end_inset
+
+.
+ Toree velja
+\begin_inset Formula $x=ah'=bh''$
+\end_inset
+
+.
+ Množimo s
+\begin_inset Formula $h'^{-1}\Rightarrow a=bh''h'^{-1}\Rightarrow aH=bh''\left(h'^{-1}H\right)\overset{\ref{enu:-1}}{=}bh''H\overset{\ref{enu:-1}}{=}bH$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Enumerate
+...
+\end_layout
+
+\begin_layout Enumerate
+Očitno (pravilo krajšanja)
+\end_layout
+
+\begin_layout Enumerate
+\begin_inset Formula $\left(\Rightarrow\right)$
+\end_inset
+
+
+\begin_inset Formula $aH=Ha\Rightarrow aHa^{-1}=Haa^{-1}=H$
+\end_inset
+
+.
+
+\begin_inset Formula $\left(\Leftarrow\right)$
+\end_inset
+
+
+\begin_inset Formula $H=aHa^{-1}\overset{\cdot a^{-1}}{\Rightarrow}a^{-1}H=Ha$
+\end_inset
+
+.
+ Ker je
+\begin_inset Formula $a\in aH$
+\end_inset
+
+, je v
+\begin_inset Formula $a^{-1}\in aH$
+\end_inset
+
+ (grupa), ker je
+\begin_inset Formula $a^{-1}\in aH\cap a^{-1}H$
+\end_inset
+
+, je
+\begin_inset Formula $aH=a^{-1}H$
+\end_inset
+
+, torej
+\begin_inset Formula $a^{-1}H=Ha\Rightarrow aH=Ha$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Theorem*
+Lagrange: Če je
+\begin_inset Formula $G$
+\end_inset
+
+ končna grupa in
+\begin_inset Formula $H$
+\end_inset
+
+ podgrupa
+\begin_inset Formula $G$
+\end_inset
+
+, potem
+\begin_inset Formula $\left|H\right|$
+\end_inset
+
+ deli
+\begin_inset Formula $\left|G\right|$
+\end_inset
+
+.
+ Nadalje je število levih/desnih odsekov po
+\begin_inset Formula $H$
+\end_inset
+
+ enako
+\begin_inset Formula $\frac{\left|G\right|}{\left|H\right|}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+Naj bodo
+\begin_inset Formula $a_{1}H,a_{2}H,\dots,a_{n}H$
+\end_inset
+
+ različni odseki.
+ Tedaj
+\begin_inset Formula $\left|G\right|\overset{\ref{enu:}}{=}\left|a_{1}H\cup\cdots\cup a_{n}H\right|\overset{\text{disjunktni odseki}}{=}\sum_{i=1}^{k}\left|a_{i}H\right|=k\left|H\right|\Rightarrow k=\frac{\left|G\right|}{\left|H\right|}$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Corollary*
+Če je
+\begin_inset Formula $G$
+\end_inset
+
+ končna grupa in
+\begin_inset Formula $a\in G$
+\end_inset
+
+, potem
+\begin_inset Formula $\red a$
+\end_inset
+
+ deli
+\begin_inset Formula $\left|G\right|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Proof
+\begin_inset Formula $\left\langle a\right\rangle =\left\{ a^{k};k\in\mathbb{Z}\right\} =\left\{ e,a,\dots,a^{n-1}\right\} \overset{\text{Lagrange}}{\Rightarrow}\left\langle a\right\rangle $
+\end_inset
+
+ je gotovo podgrupa
+\begin_inset Formula $G\Rightarrow n$
+\end_inset
+
+ deli
+\begin_inset Formula $\left|G\right|$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsection
+Kaj je podgrupa edinka? Navedite nekaj primerov podgrup edink.
+ Kaj je faktorska grupa
+\begin_inset Formula $G/H$
+\end_inset
+
+ in kaj pomeni, da je operacija v
+\begin_inset Formula $G/H$
+\end_inset
+
+ dobro definirana?
+\end_layout
+
+\begin_layout Definition*
+Naj bo
+\begin_inset Formula $H$
+\end_inset
+
+ podgrupa grupe
+\begin_inset Formula $G$
+\end_inset
+
+.
+ Tedaj rečemo, da je
+\begin_inset Formula $H$
+\end_inset
+
+ podgrupa edinka, če velja
+\begin_inset Formula $\forall a\in G:aH=Ha\overset{\ref{enu:-2}}{\Leftrightarrow}\forall a\in G:aHa^{-1}=H$
+\end_inset
+
+.
+ Oznaka:
+\begin_inset Formula $H\triangleleft G$
+\end_inset
+
+.
+ Če sta
+\begin_inset Formula $G$
+\end_inset
+
+ in
+\begin_inset Formula $\left\{ e\right\} $
+\end_inset
+
+, kjer je
+\begin_inset Formula $e$
+\end_inset
+
+ enota v
+\begin_inset Formula $G$
+\end_inset
+
+, edini edinki
+\begin_inset Formula $G$
+\end_inset
+
+, je
+\begin_inset Formula $G$
+\end_inset
+
+ enostavna.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Center grupe
+\begin_inset Formula $G\sim ZG\coloneqq\left\{ a\in G;\forall x\in G:ax=xa\right\} $
+\end_inset
+
+ ZDB taki elementi
+\begin_inset Formula $G$
+\end_inset
+
+, ki komutirajo z vsemi.
+\end_layout
+
+\begin_layout Example*
+V Abelovi grupi je vsaka podgrupa edinka.
+
+\begin_inset Formula $SL_{2}\mathbb{R}\triangleleft GL_{2}\mathbb{R}$
+\end_inset
+
+
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+NAPIŠI KAJ JE TO SPECIAL LINEAR ITD
+\end_layout
+
+\end_inset
+
+.
+
+\begin_inset Formula $ZG\triangleleft G$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Definition*
+Naj bo
+\begin_inset Formula $H\triangleleft G$
+\end_inset
+
+.
+
+\begin_inset Formula $G/H\coloneqq\left\{ aH;a\in G\right\} $
+\end_inset
+
+.
+ V množico
+\begin_inset Formula $G/H$
+\end_inset
+
+ vpeljemo operacijo
+\begin_inset Formula $\left(aH\right)\left(bH\right)=\left(ab\right)H$
+\end_inset
+
+ (*).
+\end_layout
+
+\begin_layout Theorem*
+Faktorske grupe: Če je
+\begin_inset Formula $H\triangleleft G$
+\end_inset
+
+, je
+\begin_inset Formula $G/H$
+\end_inset
+
+ grupa za (*).
+\end_layout
+
+\begin_layout Proof
+Dokazati notranjost, enoto, asociativnost in inverze je trivialno.
+ Treba je še dokazati dobro definiranost, t.
+ j.
+
+\begin_inset Formula $a,a'$
+\end_inset
+
+ iz istega odseka in
+\begin_inset Formula $b,b'$
+\end_inset
+
+ iz istega odseka
+\begin_inset Formula $\Rightarrow\left(aH\right)\left(bH\right)=\left(ab\right)H=\left(a'b'\right)H=\left(a'H\right)\left(b'H\right)$
+\end_inset
+
+.
+ Ker
+\begin_inset Formula $a'\in aH\Rightarrow\exists h'\in H\ni:ah'=a'$
+\end_inset
+
+.
+ Ker
+\begin_inset Formula $b'\in bH\Rightarrow\exists h''\in H\ni:bh''=b'$
+\end_inset
+
+.
+ Sedaj
+\begin_inset Formula $\left(a'H\right)\left(b'H\right)\overset{\text{def.}}{=}\left(a'b'\right)H=\left(ah'bh''\right)H=ah'b\left(h''H\right)\overset{\ref{enu:-1}}{=}ah'bH=ah'\left(bH\right)\overset{H\text{ edinka}}{=}ah'\left(Hb\right)=a\left(h'H\right)b\overset{\ref{enu:-1}}{=}aHb=\left(ab\right)H$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsection
+Kaj je kolobar, kaj je cel kolobar? Kaj je pravilo krajšanja v kolobarjih
+ in kakšna je povezava tega pravila s celimi kolobarji? Kaj velja za končne
+ cele kolobarje?
+\end_layout
+
+\begin_layout Definition*
+Bigrupoid
+\begin_inset Formula $\left(R,+,\cdot\right)$
+\end_inset
+
+ je kolobar, če je
+\begin_inset Formula $\left(R,+\right)$
+\end_inset
+
+ abelova grupa,
+\begin_inset Formula $\left(R,\cdot\right)$
+\end_inset
+
+ polgrupa in velja
+\begin_inset Formula $\forall a,b,c\in R:a\cdot\left(b+c\right)=a\cdot b+a\cdot c\wedge\left(a+b\right)\cdot c=a\cdot c+b\cdot c$
+\end_inset
+
+ (leva in desna distributivnost).
+ Kolobar je komutativen, če je
+\begin_inset Formula $\left(R,\cdot\right)$
+\end_inset
+
+ komutativna polgrupa.
+
+\begin_inset Formula $\left(R,+,\cdot\right)$
+\end_inset
+
+ je kolobar z enoto, če je
+\begin_inset Formula $\left(R,\cdot\right)$
+\end_inset
+
+ monoid.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Direktna vsota kolobarjev: Naj bosta
+\begin_inset Formula $R$
+\end_inset
+
+ in
+\begin_inset Formula $S$
+\end_inset
+
+ kolobarja.
+
+\begin_inset Formula $R\oplus S=R\times S$
+\end_inset
+
+ je direktna vsota .
+ Definirajmo operaciji
+\begin_inset Formula $\left(r,s\right)+'\left(r',s'\right)\coloneqq\left(r+r',s+s'\right)$
+\end_inset
+
+,
+\begin_inset Formula $\left(r,s\right)\cdot'\left(r',s'\right)\coloneqq\left(r\cdot r',s\cdot s'\right)$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Center kolobarja
+\begin_inset Formula $\sim ZR\coloneqq\left\{ a\in R;\forall x\in R:ax=xa\right\} $
+\end_inset
+
+, ZDB vsi taki elementi
+\begin_inset Formula $R$
+\end_inset
+
+, ki pri množenju s poljubnim elementom kolobarja komutirajo.
+\end_layout
+
+\begin_layout Claim*
+Če sta
+\begin_inset Formula $R$
+\end_inset
+
+ in
+\begin_inset Formula $S$
+\end_inset
+
+ kolobarja, je
+\begin_inset Formula $\left(R\oplus S,+',\cdot'\right)$
+\end_inset
+
+ kolobar.
+ Nadalje: Če sta
+\begin_inset Formula $R$
+\end_inset
+
+ in
+\begin_inset Formula $S$
+\end_inset
+
+ komutativna kolobara, je tudi
+\begin_inset Formula $\left(R\oplus S,+',\cdot'\right)$
+\end_inset
+
+ komutativen kolobar.
+ Če sta z enoto, je tudi
+\begin_inset Formula $\left(R\oplus S,+',\cdot'\right)$
+\end_inset
+
+.
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+DEFINIRAJ PODKOLOBAR
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Če v kolobarju
+\begin_inset Formula $R$
+\end_inset
+
+ velja
+\begin_inset Formula $a\cdot b=0$
+\end_inset
+
+
+\begin_inset Foot
+status open
+
+\begin_layout Plain Layout
+0 je aditivna enota
+\end_layout
+
+\end_inset
+
+ in sta
+\begin_inset Formula $a\not=0$
+\end_inset
+
+ in
+\begin_inset Formula $b\not=0$
+\end_inset
+
+, sta
+\begin_inset Formula $a$
+\end_inset
+
+ in
+\begin_inset Formula $b$
+\end_inset
+
+ delitelja niča.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+V kolobarju
+\begin_inset Formula $\left(R,+,\cdot\right)$
+\end_inset
+
+ velja pravilo krajšanja, če velja
+\begin_inset Formula $\forall a,b,c\in R,a\not=0:ab=ac\Rightarrow b=c$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Standard
+\begin_inset Separator plain
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Komutativen kolobar z enoto
+\begin_inset Formula $1\not=0$
+\end_inset
+
+ (ZDB multiplikativna enota ni enaka aditivni) brez deliteljev niča je
+\series bold
+cel
+\series default
+.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $\left(\mathbb{Z},+,\cdot\right)$
+\end_inset
+
+ je cel, toda
+\begin_inset Formula $\left(\mathbb{Z}_{6},+_{6},\cdot_{6}\right)$
+\end_inset
+
+ ni cel, ker premore delitelje niča.
+\end_layout
+
+\begin_layout Theorem*
+Naj bo
+\begin_inset Formula $\left(R,+,\cdot\right)$
+\end_inset
+
+ komutativen kolobar z enoto
+\begin_inset Formula $1\not=0$
+\end_inset
+
+.
+ Velja
+\begin_inset Formula $R$
+\end_inset
+
+ cel
+\begin_inset Formula $\Leftrightarrow$
+\end_inset
+
+ v
+\begin_inset Formula $R$
+\end_inset
+
+ velja pravilo krajšanja.
+\end_layout
+
+\begin_layout Proof
+Dokazujemo ekvivalenco:
+\end_layout
+
+\begin_deeper
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(\Rightarrow\right)$
+\end_inset
+
+ Predpostavimo, da je
+\begin_inset Formula $R$
+\end_inset
+
+ cel.
+ Predpostavimo
+\begin_inset Formula $ab=ac$
+\end_inset
+
+ za poljuben
+\begin_inset Formula $a\not=0$
+\end_inset
+
+ in poljubna
+\begin_inset Formula $b,c$
+\end_inset
+
+.
+ Računamo:
+\begin_inset Formula $ab=ac\Leftrightarrow ab-ac=0\Leftrightarrow a\left(b-c\right)=0$
+\end_inset
+
+.
+ Ker je
+\begin_inset Formula $R$
+\end_inset
+
+ cel in
+\begin_inset Formula $a\not=0$
+\end_inset
+
+, mora biti
+\begin_inset Formula $b-c=0$
+\end_inset
+
+, sicer bi bila
+\begin_inset Formula $a$
+\end_inset
+
+ in
+\begin_inset Formula $b-c$
+\end_inset
+
+ delitelja niča, kar bi bilo v
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+ s predpostavko o celosti
+\begin_inset Formula $R$
+\end_inset
+
+.
+
+\begin_inset Formula $b-c=0\Rightarrow b=c$
+\end_inset
+
+, torej
+\begin_inset Formula $\forall a\not=0,b,c\in R:ab=ac\Rightarrow b=c\sim$
+\end_inset
+
+ velja pravilo krajšanja.
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $\left(\Leftarrow\right)$
+\end_inset
+
+ Predpostavimo, da v komutativnem kolobarju z enoto
+\begin_inset Formula $1\not=0$
+\end_inset
+
+
+\begin_inset Formula $R$
+\end_inset
+
+ velja pravilo krajšanja.
+ Predpostavimo
+\begin_inset Formula $ab=0$
+\end_inset
+
+,
+\begin_inset Formula $a\not=0$
+\end_inset
+
+.
+ Dokazati je treba
+\begin_inset Formula $b=0$
+\end_inset
+
+, sicer bi imeli delitelje niča.
+ Velja
+\begin_inset Formula $ab=0=a\cdot0$
+\end_inset
+
+.
+ Uporabimo pravilo krajšanja na
+\begin_inset Formula $ab=a0$
+\end_inset
+
+ in dobimo
+\begin_inset Formula $b=0$
+\end_inset
+
+.
+ Kolobar je cel.
+\end_layout
+
+\end_deeper
+\begin_layout Definition*
+Komutativen kolobar
+\begin_inset Formula $R$
+\end_inset
+
+ z enoto
+\begin_inset Formula $1\not=0$
+\end_inset
+
+ je
+\series bold
+obseg
+\series default
+, če je vsak neničeln element obrnljiv v
+\begin_inset Formula $\left(R,\cdot\right)$
+\end_inset
+
+ ZDB
+\begin_inset Formula $\left(R\setminus\left\{ 0\right\} ,\cdot\right)$
+\end_inset
+
+ je grupa.
+ Obseg
+\begin_inset Formula $R$
+\end_inset
+
+ je polje, če je
+\begin_inset Formula $\left(R\setminus\left\{ 0\right\} ,\cdot\right)$
+\end_inset
+
+ abelova grupa ZDB
+\begin_inset Formula $ZR=R$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Theorem*
+Če je
+\begin_inset Formula $\left(R,+,\cdot\right)$
+\end_inset
+
+ končen cel kolobar
+\begin_inset Formula $\Rightarrow R$
+\end_inset
+
+ polje.
+\end_layout
+
+\begin_layout Proof
+Dokažimo, da
+\begin_inset Formula $\forall a\in R,a\not=0\exists a^{-1}\ni:aa^{-1}=1$
+\end_inset
+
+.
+ Naj bo
+\begin_inset Formula $a\in R$
+\end_inset
+
+ poljuben, z izjemo
+\begin_inset Formula $a\not=0$
+\end_inset
+
+.
+ Oglejmo si
+\begin_inset Formula $\left\{ a^{k};\forall k\geq0\right\} $
+\end_inset
+
+ ZDB množico vseh potenc
+\begin_inset Formula $a$
+\end_inset
+
+.
+ Ker
+\begin_inset Formula $\left|R\right|<\infty\Rightarrow\exists i,j,$
+\end_inset
+
+BSŠ
+\begin_inset Formula $i>j\ni a^{i}=a^{j}$
+\end_inset
+
+ ZDB ker je
+\begin_inset Formula $R$
+\end_inset
+
+ končen, se nek element
+\begin_inset Quotes gld
+\end_inset
+
+ponovi
+\begin_inset Quotes grd
+\end_inset
+
+.
+
+\begin_inset Formula $a^{j}\cdot a^{i-j}=a^{i}=a^{j}=a^{j}\cdot1$
+\end_inset
+
+ Ker je kolobar cel,
+\begin_inset Formula $a^{j}\not=0$
+\end_inset
+
+ in ker velja pravilo krajšanja,
+\begin_inset Formula $a^{i-j}=1$
+\end_inset
+
+, pri čemer vemo, da je
+\begin_inset Formula $i-j>0$
+\end_inset
+
+.
+ Ločimo dva primera:
+\end_layout
+
+\begin_deeper
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $i-j=1$
+\end_inset
+
+
+\begin_inset Formula $a=1\Rightarrow a$
+\end_inset
+
+ je kot multiplikativna enota multiplikativni inverz sam sebi
+\end_layout
+
+\begin_layout Labeling
+\labelwidthstring 00.00.0000
+\begin_inset Formula $i-j>1$
+\end_inset
+
+
+\begin_inset Formula $a=a\cdot a^{i-j-1}=1$
+\end_inset
+
+, torej
+\begin_inset Formula $a^{i-j-1}$
+\end_inset
+
+ je inverz
+\begin_inset Formula $a$
+\end_inset
+
+.
+\end_layout
+
+\end_deeper
+\begin_layout Subsection
+Kaj je karakteristika kolobarja? Kako lahko določimo karakteristiko kolobarja
+ z enoto? Kaj lahko povemo o karakteristiki celega kolobarja?
+\end_layout
+
+\begin_layout Definition*
+Karakteristika kolobarja
+\begin_inset Formula $R\sim\karakteristika R$
+\end_inset
+
+ je najmanjši
+\begin_inset Formula $n\in\mathbb{N}\ni:\forall a\in R:a+\cdots_{n-\text{krat}}\cdots+a=0$
+\end_inset
+
+.
+ Če tak
+\begin_inset Formula $n$
+\end_inset
+
+ ne obstaja, pravimo
+\begin_inset Formula $\karakteristika R=0$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Theorem*
+Naj bo
+\begin_inset Formula $\left(R,+,\cdot\right)$
+\end_inset
+
+ kolobar z enoto.
+
+\begin_inset Formula $\karakteristika R=\red1$
+\end_inset
+
+ v grupi
+\begin_inset Formula $\left(R,+\right)$
+\end_inset
+
+ ZDB red enote v aditivni grupi.
+\end_layout
+
+\begin_layout Proof
+Po definiciji reda je
+\begin_inset Formula $1+\cdots_{\red1-\text{krat}}\cdots+1=0$
+\end_inset
+
+ in za nek
+\begin_inset Formula $m<\red1$
+\end_inset
+
+
+\begin_inset Formula $1+\cdots_{m-\text{krat}}\cdots+1\not=0$
+\end_inset
+
+, torej
+\begin_inset Formula $\karakteristika R\geq\red1$
+\end_inset
+
+.
+ Sedaj vzemimo poljuben
+\begin_inset Formula $a\in R$
+\end_inset
+
+.
+ Velja
+\begin_inset Formula $a+\cdots_{\red1-\text{krat}}\cdots+a=1\cdot a+\cdots_{\red1-\text{krat}}\cdots+1\cdot a=a\cdot\left(1+\cdots_{\red1-\text{krat}}\cdots+1\right)=a\cdot0=0$
+\end_inset
+
+, torej
+\begin_inset Formula $\karakteristika R\leq\red1$
+\end_inset
+
+, torej
+\begin_inset Formula $\karakteristika R=\red1$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Theorem*
+Naj bo
+\begin_inset Formula $\left(R,+,\cdot\right)$
+\end_inset
+
+ cel kolobar.
+ Tedaj velja bodisi
+\begin_inset Formula $\karakteristika R=0$
+\end_inset
+
+ bodisi
+\begin_inset Formula $\karakteristika R=p$
+\end_inset
+
+, kjer je
+\begin_inset Formula $p$
+\end_inset
+
+ praštevilo.
+\end_layout
+
+\begin_layout Proof
+Če je
+\begin_inset Formula $\karakteristika R=0$
+\end_inset
+
+, smo dokazali, sicer je
+\begin_inset Formula $\karakteristika R=r>0$
+\end_inset
+
+.
+ PDDRAA
+\begin_inset Formula $n=pq$
+\end_inset
+
+ za
+\begin_inset Formula $p,q>1$
+\end_inset
+
+ in
+\begin_inset Formula $p,q\in\mathbb{N}$
+\end_inset
+
+.
+ Po prejšnjem izreku
+\begin_inset Formula $\karakteristika R=\red1=n$
+\end_inset
+
+.
+ Tedaj velja
+\begin_inset Formula $0=1+\cdots_{n-\text{krat}}\cdots+1=1+\cdots_{pq-\text{krat}}\cdots+1=\left(1+\cdots_{p-\text{krat}}\cdots+1\right)\cdot\left(1+\cdots_{q-\text{krat}}\cdots+1\right)=a\cdot b$
+\end_inset
+
+.
+ Ker smo v celem kolobarju, je bodisi
+\begin_inset Formula $a=0$
+\end_inset
+
+, bodisi
+\begin_inset Formula $b=0$
+\end_inset
+
+, toda to je
+\begin_inset Formula $\rightarrow\!\leftarrow$
+\end_inset
+
+, saj bi bil potem
+\begin_inset Formula $\red1=q$
+\end_inset
+
+ ali
+\begin_inset Formula $\red1=p$
+\end_inset
+
+, oboje pa je
+\begin_inset Formula $<pq$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Subsection
+Kaj je ideal kolobarja? Kako lahko preverimo, ali je
+\begin_inset Formula $I\subseteq R$
+\end_inset
+
+ ideal kolobarja
+\begin_inset Formula $R$
+\end_inset
+
+? Kaj je faktorski kolobar
+\begin_inset Formula $R/I$
+\end_inset
+
+ in kako računamo v njem?
+\end_layout
+
+\begin_layout Definition*
+Če je
+\begin_inset Formula $R$
+\end_inset
+
+ kolobar, je njegov podkolobar
+\begin_inset Formula $S$
+\end_inset
+
+ ideal, če velja
+\begin_inset Formula $\forall v\in R,s\in S:rs,sr\in S$
+\end_inset
+
+ ZDB to je podkolobar, zaprt za zunanje množenje.
+\end_layout
+
+\begin_layout Example*
+\begin_inset Formula $n\cdot\mathbb{Z}$
+\end_inset
+
+ (večkratniki
+\begin_inset Formula $n$
+\end_inset
+
+) za fiksen
+\begin_inset Formula $n$
+\end_inset
+
+ so ideal v
+\begin_inset Formula $\mathbb{Z}$
+\end_inset
+
+.
+
+\begin_inset Formula $\mathbb{Z}$
+\end_inset
+
+ je podkolobar v
+\begin_inset Formula $\mathbb{Q}$
+\end_inset
+
+, toda ni njegov ideal.
+\end_layout
+
+\begin_layout Claim*
+\begin_inset Formula $I\subseteq R$
+\end_inset
+
+ je ideal
+\begin_inset Formula $\Leftrightarrow0\in I$
+\end_inset
+
+ (vsebuje aditivno enoto)
+\begin_inset Formula $\wedge\forall i,j\in I:i-j\in I$
+\end_inset
+
+ (zaprt za odštevanje)
+\begin_inset Formula $\wedge\forall i\in I,r\in R:ir\in I,ri\in I$
+\end_inset
+
+ (zaprt za zunanje množenje)
+\begin_inset Note Note
+status open
+
+\begin_layout Plain Layout
+TODO XXX FIXME vsota in produkt idealov je spet ideal
+\end_layout
+
+\end_inset
+
+
+\end_layout
+
+\begin_layout Definition*
+Naj bo
+\begin_inset Formula $R$
+\end_inset
+
+ kolobar in
+\begin_inset Formula $I$
+\end_inset
+
+ ideal v
+\begin_inset Formula $R$
+\end_inset
+
+.
+ Faktorski kolobar:
+\begin_inset Formula $R/I=\left\{ a+I,\forall a\in R\right\} =\left\{ \left\{ a+i;\forall i\in I\right\} ;\forall a\in R\right\} $
+\end_inset
+
+ vsebuje aditivne odseke.
+ V
+\begin_inset Formula $R/I$
+\end_inset
+
+ vpeljemo operaciji:
+\begin_inset Formula $\left(a+I\right)+'\left(b+I\right)=a+b+I$
+\end_inset
+
+ in
+\begin_inset Formula $\left(a+I\right)\cdot$
+\end_inset
+
+'
+\begin_inset Formula $\left(b+I\right)=a\cdot b+I$
+\end_inset
+
+.
+\end_layout
+
+\begin_layout Theorem*
+Če je
+\begin_inset Formula $I$
+\end_inset
+
+ ideal v
+\begin_inset Formula $R$
+\end_inset
+
+, je
+\begin_inset Formula $\left(R/I,+',\cdot'\right)$
+\end_inset
+
+ kolobar.
+\end_layout
+
+\end_body
+\end_document
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-07 15:09:51 +0100