index.md (1116B)
1 +++ 2 title = 'Graphs' 3 +++ 4 # Graphs 5 ## What is a graph? 6 7 a set of vertices (nodes) and a set of edges (arc/arrows) connecting pairs of vertices 8 9 consists of a collection *V* of vertices and collection *E* of edges, for which we write *G = (V, E)* 10 11 each edge e ∈ E is said to join two vertices (end points) 12 if *e* joins *u*, v ∈ *V*, we write *e = (u, v)* 13 14 *V* — finite set of vertices 15 *E* — set of edges (pairs of vertices) 16 17 *V = {a, b, c, d, e, f}* 18 19 *E = {(a,c), (a,d), (b,c), (b,f), (c,e), (d,e), (e,f)}* 20 21 [Types of graphs](./types-of-graphs) 22 23 ## Completeness 24 25 A graph is complete if you have *n* vertices and *n-1 *edges on each vertex. Must be simple and undirected. 26 27 ## Edges properties 28 29 - connects two vertices 30 - an edge connecting vertices *i *and *j* is written as *ij* 31 - sometimes has a direction (*i —> j*) 32 - weights assigned by means of numbers (e.g. distance between two vertices) 33 34 ## Adjacency Matrix representation 35 Notation: A[i,j] 36 37 Symmetric: A[i,j] = A[j,i] 38 39 when a graph is undirected, the adjacency matrix is always symmetric 40 41 