or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Syncing
xxxxxxxxxx
Operacijske raziskave - vaje 20.4.2020
Algoritmi na grafih
Graf: \(G = (V, E)\)
\[ \begin{aligned} n &= |V| \\ m &= |E| + |V| \\ d(u) &= |\{\{u, v\} \in E \mid v \in V\}| \\ d^+(u) &= |\{(u, v) \in E \mid v \in V\}| \\ d^-(u) &= |\{(u, v) \in E \mid v \in V\}| \end{aligned} \]
Predstavitev grafa:
Naloga 1
Zasnuj podatkovno strukturo za grafe, ki temelji na matrični predstavitvi. Podatkovna struktura naj ima sledeče metode:
__init__(G)
: ustvarjanje praznega grafadodajVozlisce(G, u)
: dodajanje novega vozliščadodajPovezavo(G, u, v)
: dodajanje nove povezavebrisiPovezavo(G, u, v)
: brisanje povezavebrisiVozlisce(G, u)
: brisanje vozliščasosedi(G, u)
: seznam sosedov danega vozliščaZa vsako od naštetih metod podaj tudi njeno časovno zahtevnost v odvisnosti od števila vozlišč, števila povezav in stopenj vhodnih vozlišč. Oceni tudi prostorsko zahtevnost celotne strukture.
Naloga 2
Zasnuj podatkovno strukturo za grafe, ki temelji na seznamih sosedov. Zapiši metode kot pri prejšnji strukturi ter oceni njihovo časovno zahtevnost in prostorsko zahtevnost celotne strukture.
Naloga 3
Kako moramo spremeniti prejšnji strukturi, da bosta predstavljali digrafe?
Naloga 4
Napiši algoritem, ki za vhodni graf \(G\) določi, ali ima trikotnik. Katero podatkovno strukturo za grafe boš uporabil?
Naloga 5
Dan je digraf \(D = (V, E)\). Pravimo, da je vozlišče \(v \in V\) zvezda digrafa \(D\), če ima izhodno povezavo do vseh ostalih vozlišč in v digrafu \(D\) ni drugih povezav. Napiši algoritem, ki poišče zvezdo danega digrafa, če ta obstaja.