Samenvatting

Networks and Graphs Summary

2 keer verkocht

Instelling
Vrije Universiteit Amsterdam (VU)

Summary of the slides of Jacopo Urbani and Ali Mehrabi based on the book "Graph Theory and Complex Networks" by Maarten van Steen. It discusses chapters 2, 3, 4, 5, 6, 7, and 9. *Study material of following years may differ*

[Meer zien]

Voorbeeld 2 van de 10 pagina's

Bekijk voorbeeld

Geupload op 22 oktober 2021
Aantal pagina's 10
Geschreven in 2020/2021
Type Samenvatting

networks and graphs
networks
graphs
foundations
extensions
network traversal
trees
network analysis
random networks
social networks
connectivity
vertex and edge cuts
k connectivity
mengers theorem

Volgen

syntryx Lid sinds 6 jaar 64 documenten verkocht

€6,49

In winkelwagen

Op verlanglijstje

100% tevredenheidsgarantie
Direct beschikbaar na je betaling
Lees online óf als PDF
Geen vaste maandelijkse kosten

X_401010 Networks and Graphs
Index

Chapter 2 - Foundations ....................................................................................................................................1
Chapter 3 - Extensions ......................................................................................................................................3
Chapter 4 - Network Traversal ..........................................................................................................................3
Chapter 5 - Trees ...............................................................................................................................................5
Chapter 6 - Network Analysis ...........................................................................................................................6
Chapter 7 - Random Networks..........................................................................................................................7
Chapter 9 - Social Networks .............................................................................................................................8

Chapter 2 - Foundations

➤2.1 Graphs & Degrees
• Graph(G): Consists of V(G) set of vertices and E(G) set of edges.
• Edge: Connects 2 vertices u and v and is denoted by ⟨u, v⟩.
• For any u ∈ V(G) the neighbor set N(u) is the set of all vertices adjacent to u except for u itself.
• A graph is simple if it does not contain multiple edges between the same pair of vertices nor loops.
• The degree δ(v) of a vertex is the number of edges attached to vertex v. Loops are counted twice.
• Handshaking lemma: ∑v ∈ V(G)δ(v) = 2 |E(G)| for all graphs G, meaning for any graph the sum of the
degrees of vertices equals 2 times the number of edges in the graph.
• Degree sequence: A list of the degrees of the vertices in a graph. It is ordered if the numbers are in
non-increasing order. E.g. [1,0,0] & [2,2,2]
• A sequence of numbers is graphic if it is the degree sequence of a simple graph. E.g. [2,2,2]

➤2.2 Two Ways of Graph Representation
• Properties of an adjacency matrix:
- Symmetry i.e. ∀u, v : A[u, v] = A[v, u]
- Whether a graph is simple or not i.e. ∀u, v : A[u, v] ≤ 1 and A[u, u] = 0
- The sum of the numbers on each row should be equal to the degree of that vertex.
• Properties of an incidence matrix:
- The sum of the numbers in each column must be exactly 2.
- The sum of the numbers on each row should be equal to the degree of that vertex.

Fig.1.1 Example graph Fig.1.2 Matrices for the graph (1):Adjacency (2):Incidence
➤2.3 Subgraphs
• H is a subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G) and for all ⟨u, v⟩ ∈ E(H) there is u, v ∈ V(H).
• G[V*]: Subgraph induced by V* ⊆ V(G) has vertex set V* and edge set {⟨u, v⟩ ∈ E(G) | u, v ∈ V*}.
• G[E*]: Subgraph induced by E* ⊆ E(G) has edge set E* and vertex set {u, v ∈ V(G) | ⟨u, v⟩ ∈ E*}.

➤2.4 Graph Isomorphisms
• Graphs G1 and G2 are isomorphic if there is a one-to-one mapping. φ : V(G1) → V(G2). The graphs
have vertices with the same combinations of edges.
• For 2 graphs to be isomorphic it has to have the same amount of vertices, edges, and the ordered
degree sequence of the graphs have to be the same.
• Further it can be determined by the naïve algorithm or the Babai and Luks algorithm.

➤2.5 The Theorem of Havel-Hakimi
• Let [s, t1, t2, …, ts, d1, …, dn] be an ordered sequence. This sequence is graphic if and only if the
sequence [t1 - 1, t2 - 1, …, ts - 1, d1, …, dn] is graphic too.
• To determine this with the Havel-Hakimi theorem, continuously apply the “only if direction” (erase
the most left vertex) until the base case is reached. Then determine whether the base case is graphic.
• E.g. [4,4,2,2,2] => [3,1,1,1] => [0,0,0]. [0,0,0] is graphic, therefore [4,4,2,2,2] is graphic.
1

, ➤2.7 Paths, Cycles and Connectivity
• A (v0, vk)-walk is a sequence [v0, e1, v1, e2, …, vk - 1, ek, vk] with ei = ⟨vi - 1, vi⟩ for all i = 1,…,k.
• A (u, v)-path is a (u, v)-walk over distinct vertices.
• In a simple graph, a cycle is a (u, v)-path of at least 3 edges over distinct vertices except u = v.
• If a simple graph does not contain any cycles, it is acyclic.
• Two vertices u, v in G are connected if there is a (u, v)-path in G.
• Connectivity indicates that each vertex can be reached by any other vertex in the network.
• A component of a graph G is a connected subgraph that is not strictly contained in another connected
subgraph of G.

➤2.8 Vertex and Edge Cuts
• V* ⊆ V(G) is a vertex cut of G if removing the vertices in V* (and their edges) from G yields a non-
connected graph.
• E* ⊆ E(G) is an edge cut of G if removing the edge in E* from G yields a non-connected graph.
• It is of interest to find the minimum number of vertices or edges to remove for a graph to fall apart. So,
κ(G) is the minimum vertices that need to be removed, and λ(G) is the minimum number of edges.
• κ(G) ≤ λ(G) ≤ minv ∈ V(G){δ(v)}(minimum degree of G)

➤2.8 K-Connectivity and Harary Graphs
• A graph G is k-connected if κ(G) ≥ k vertices. Meaning you can’t disconnect Hk, n by removing less
than k vertices.
• Harary graph(Hk, n): A k-connected simple graph with n vertices and with a minimal number of
edges. There are 3 cases for combinations of k and n.
- k is even: Connect each vertex to its k/2 closest left-hand & right-hand neighbors.
- k is odd, n is even: Construct Hk-1, n and add n/2 edges, joining vertices at n/2 distance(opposites)
- k is odd, n is odd: Construct Hk-1, n and add the (n+1)/2 edges, joining vertices at (n-1)/2 distance
• The vertices in all have degree k, except if k and n are both odd, then vertex (n-1)/2 has degree k + 1.

➤2.9 Menger’s Theorem
• Let P(u, v) be a set of (u, v)-paths in a simple graph:
- Vertex independent: ∀P, Q ∈ P(u, v) : V(P) ∩ V(Q) = {u, v}, different paths that have only u and
v in common.
- Edge independent: ∀P, Q ∈ P(u, v) : E(P) ∩ E(Q) = ∅, different paths don’t share any edges.
• Menger’s Theorem: The minimum size of a vertex cut disconnecting nonadjacent vertices u ≠ v
equals the maximum size of a vertex-independent set P(u, v). The minimum size of an edge cut
disconnecting vertices u ≠ v equals the maximum size of an edge-independent set P(u, v).

➤2.10 Bipartite Graphs
• A graph G is bipartite if V(G) = V1 ∪ V2 (G is split in two) such that:
- V1 ∩ V2 = ∅; they don’t have shared vertices
- E(G) ⊆ {⟨u, v⟩ | v1 ∈ V1 and v2 ∈ V2 }; any edge of G must connect a vertex from V1 to one of V2.
• Bipartite graphs are often drawn as ranked embeddings. This will make it more obvious to say
whether a graph is bipartite or not. A ranked embedding is made as follows:
- Choose a vertex and put all the vertices where they’re connected to through an edge in a
horizontal row above. Do the same with those vertices until all vertices are in a row.
- If all the vertices on the same row do not have an edge connected them, the graph is bipartite.
- The number of rows is the number of possible disjoint subsets.
➤2.11 Planar Graphs & Euler’s Formula
• A simple and connected graph is planar if there exists a drawing in the 2D plane such that no two
edges cross.
• In any planar graph of n ≥ 1 vertices, m ≥ 0 edges and r ≥ 1 regions (regions closed off because of
edges and vertices, including the exterior region), then n − m + r = 2. This is the Euler’s formula.
• For any planar graph G with n ≥ 3 vertices and m edges: m ≤ 3n − 6.
• Every planar graph G has at least one vertex v with δ(v) ≤ 5.

2

Dit zijn jouw voordelen als je samenvattingen koopt bij Stuvia:

Bewezen kwaliteit door reviews

Studenten hebben al meer dan 850.000 samenvattingen beoordeeld. Zo weet jij zeker dat je de beste keuze maakt!

In een paar klikken geregeld

Geen gedoe — betaal gewoon eenmalig met iDeal, creditcard of je Stuvia-tegoed en je bent klaar. Geen abonnement nodig.

Direct to-the-point

Studenten maken samenvattingen voor studenten. Dat betekent: actuele inhoud waar jij écht wat aan hebt. Geen overbodige details!

Veelgestelde vragen

Wat krijg ik als ik dit document koop?

Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.

Tevredenheidsgarantie: hoe werkt dat?

Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.

Van wie koop ik deze samenvatting?

Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper syntryx. Stuvia faciliteert de betaling aan de verkoper.

Zit ik meteen vast aan een abonnement?

Nee, je koopt alleen deze samenvatting voor €6,49. Je zit daarna nergens aan vast.

Is Stuvia te vertrouwen?

4,6 sterren op Google & Trustpilot (+1000 reviews)

Afgelopen 30 dagen zijn er 69052 samenvattingen verkocht

Opgericht in 2010, al 15 jaar dé plek om samenvattingen te kopen

Begin nu gratis

Samenvatting

Networks and Graphs Summary

Document informatie

Onderwerpen

Geschreven voor

Verkoper

Ontvangen beoordelingen

Voorbeeld van de inhoud