#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.
 
\family default
Nekateri bi 
\begin_inset Formula $\left\{ 1..n\right\} $
\end_inset

 označili z 
\begin_inset Formula $\left[n\right]$
\end_inset

.
\end_layout

\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'\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