Graph Theory and Complex Networks – Maarten van Steen
Chapter 1
Cycle: meerdere paden tussen twee knopen
Tree: simpel netwerk, zonder cycles
Internet zorgde voor location independent communication
Packet switching is het wisselen van naar wie je het pakket levert
Circuit switching is het wisselen van soort pakket over een vast circuit
Een netwerk is connected als een bericht van iedereen naar iedereen kan.
Small world, klein aantal 'degrees of seperation'
Chapter 2
Een edge joint twee vertices.
De vertices zijn dan adjacent, de edge is incident with de vertices
e = <u, v>
Simple graph heeft geen loops of multiple edges
Complete graph, Kn
Complement of a graph: alles losmaken en verbindingen maken waar die nog niet
waren, G_ (streepje erboven)
Degree is aantal vertices die incident zijn met een vertex, delta(g)
Som van degrees is twee keer zo groot als het aantal edges
Absoluutstrepen geven grootte aan van een verzameling
Het aantal vertices met een oneven degree, is even
(ordered) degree sequence: opeenvolging van degrees (in aflopende volgorde)
Een k-regular graph bestaat uit vertices met degree k.
3-regular graph is een cubic graph
Een degree sequence kan een grafiek vormen als deze methode werkt:
- Verwijder de hoogste degree
- Verminder dat aantal knopen met 1
- Ga door bij de volgende, tot er niks overblijft, dan klopt het
Zelfde degree sequence hoeft niet zelfde grafiek te hebben
Proof by construction, voorbeelden noemen
Induced by..
E ∪ E- (union, vereniging), corresponds to Kn
Line graph: alle lijnen worden knopen en als twee lijnen verbonden waren met een
knoop, wordt daar een lijn tussen getrokken.
Induced graph door verwijderen knoop of lijn: G[V(G)\{v}], bij verwijderen lijn kan je
zeggen G - e i.p.v. G[E(G)\{e}]
A (v0, vk)-walk in G is an alternating sequence [v0, e1, v1, e2 . . . vk−1 , ek , vk ] of
vertices and edges from G with ei = <vi−1 , vi>.
Bij een closed walk, v0 = vk, begin en eindpunt zijn hetzelfde
Een trail is een route in met alleen verschillende edges
Een path is een trail waarbij alle vertices verschillend zijn.
Chapter 1
Cycle: meerdere paden tussen twee knopen
Tree: simpel netwerk, zonder cycles
Internet zorgde voor location independent communication
Packet switching is het wisselen van naar wie je het pakket levert
Circuit switching is het wisselen van soort pakket over een vast circuit
Een netwerk is connected als een bericht van iedereen naar iedereen kan.
Small world, klein aantal 'degrees of seperation'
Chapter 2
Een edge joint twee vertices.
De vertices zijn dan adjacent, de edge is incident with de vertices
e = <u, v>
Simple graph heeft geen loops of multiple edges
Complete graph, Kn
Complement of a graph: alles losmaken en verbindingen maken waar die nog niet
waren, G_ (streepje erboven)
Degree is aantal vertices die incident zijn met een vertex, delta(g)
Som van degrees is twee keer zo groot als het aantal edges
Absoluutstrepen geven grootte aan van een verzameling
Het aantal vertices met een oneven degree, is even
(ordered) degree sequence: opeenvolging van degrees (in aflopende volgorde)
Een k-regular graph bestaat uit vertices met degree k.
3-regular graph is een cubic graph
Een degree sequence kan een grafiek vormen als deze methode werkt:
- Verwijder de hoogste degree
- Verminder dat aantal knopen met 1
- Ga door bij de volgende, tot er niks overblijft, dan klopt het
Zelfde degree sequence hoeft niet zelfde grafiek te hebben
Proof by construction, voorbeelden noemen
Induced by..
E ∪ E- (union, vereniging), corresponds to Kn
Line graph: alle lijnen worden knopen en als twee lijnen verbonden waren met een
knoop, wordt daar een lijn tussen getrokken.
Induced graph door verwijderen knoop of lijn: G[V(G)\{v}], bij verwijderen lijn kan je
zeggen G - e i.p.v. G[E(G)\{e}]
A (v0, vk)-walk in G is an alternating sequence [v0, e1, v1, e2 . . . vk−1 , ek , vk ] of
vertices and edges from G with ei = <vi−1 , vi>.
Bij een closed walk, v0 = vk, begin en eindpunt zijn hetzelfde
Een trail is een route in met alleen verschillende edges
Een path is een trail waarbij alle vertices verschillend zijn.
