Graph Theoey

Question 1

Simple graph

Answer 1

A finite, non-empty set V(G) of elements called vertices, together with a possibly empty set E(G) of 2-element subsets of V(G), called edges where uv denotes the egde between a vertex u eV(G) and vertex v eV(G)

Question 2

Order

Answer 2

Number of vertices, p

Question 3

Size

Answer 3

Number of edges, q

Question 4

Density

Answer 4

Relationship between number of edges and number of possible edges
q(G) /(p(G)c2)

Question 5

Multigraph

Answer 5

More than 1 edge between vertices

Question 6

Pseudograph

Answer 6

Contains a loop

Question 7

Open neighbourhood

Answer 7

All vertices surrounding a vertex Ng(v)

Question 8

Closed Neighbourhood

Answer 8

All vertices surrounding the vertex and the vertex itself Ng[V]

Question 9

Incident

Answer 9

Edge and vertex are touching

Question 10

Degree

Answer 10

DegG(Vi) number of vertices adjacent to vertex i

Question 11

Isolated vertex

Answer 11

Degree 0

Question 12

End vertex

Answer 12

Degree 1

Question 13

Even vertex

Answer 13

Even degree, include isolated vertices

Question 14

Minimum degree

Answer 14

Lowest degree of a vertex small delta

Question 15

Maximum degree

Answer 15

Maximum degree of a vertex big delta

Question 16

Fundamental thm of graph theory (thm 2.1)

Answer 16

S(from 1 to p) deg(vi) =2q

Question 17

Corollary of 2.1

Answer 17

Every graph has an even number of odd vertices

Question 18

Subgraph

Answer 18

V(H) is a subset of V(G) and E(H) is a sunset of E(G)

Question 19

Propper subgraph

Answer 19

Can’t be exactly the same

Question 20

Spanning subgraph

Answer 20

Vertices exactly the same, but not all edges

are there

Question 21

Edge induced subgraph

Answer 21

G non empty subset T is a subset of E(G) and vertex set V()
(no isolated vertices)

Question 22

Walk

Answer 22

Finite alternating sequence of vertices and edges from v1 to vn

Question 23

Path

Answer 23

A walk with no repeated vertices (therefore no repeated edges)

Question 24

Distance

Answer 24

dG1(vi, vj) shortest path between the two vertices

Question 25

Cycle

Answer 25

Path where you end where you started

Question 26

Acyclic graph

Answer 26

Graph with no cycles

Question 27

Trail

Answer 27

No repeates edges (vertices don't matter)

Question 28

Circuit

Answer 28

Trail that closes

Question 29

Connected graph

Answer 29

There is a path between every vertex in the graph

Question 30

Disconnected graph

Answer 30

There are at least 2 vertices in the graph where there is no path between them

Question 31

Component

Answer 31

"seperate bits"

Question 32

Bridge

Answer 32

Edge which, if removed will increase the number of components of the graph

Question 33

Cut vertex

Answer 33

Vertex which, if removed, increases the number of components

Question 34

R-regular

Answer 34

All vertices have degree r

Question 35

Complete graph of order n

Answer 35

Has all possible edges: (n-1) regular (nc2) edges

Question 36

Partite set

Answer 36

No edges between vertices in set

Question 37

Complete multipartite graph

Answer 37

Complete graph within partite sets

Question 38

Planar graph

Answer 38

Graph that can be drawn with no edges crossing

Question 39

Plane graph

Answer 39

Graph that is drawn with no edges crossing

Question 40

Kuratowski's thm

Answer 40

Graph is planar iff it doesn't contain K5 or K3, 3

Question 41

Nonplanar graph

Answer 41

Can't be drawn without edges crossing

Question 42

Tree

Answer 42

Acyclic connected graph, order n implies size n-1

Question 43

Spanning tree

Answer 43

(a subgraph) tree ensuring a path between any 2 vertices

Question 44

Adjacency matrix

Answer 44

Represents graph: 1 for edge 0 for no edge | Use capital letter: A(G2) =...

Question 45

Directed graph

Answer 45

Finite, nonempty set V(D) of elements called vertices, together with a possibly empty set E(D) of ORDERED pairs of distinct vertices of D, called arcs where (u, v) denotes the arc from a vertex u to a vertex v *element of* V(D)

Question 46

Out-neighbourhood

Answer 46

ND+ - open neighbourhood of all vertices adjacent FROM starting vertex

Question 47

In neighbourhood

Answer 47

Open neighbourhood of all vertices adjacent TO starting vertex ND-(V)

Question 48

Out degree

Answer 48

Cardibality of out neighbourhood of vertex

Question 49

In degree

Answer 49

Cardinality of in neighbourhood of vertex

Question 50

Degree of vertex in directed graph

Answer 50

degD(v) = odD(v) + idD(v) | out degree of D(v) + in degree of D(v)

Question 51

Ist theorem of digraph

Answer 51

Sum of all out degrees = sum of in degrees = q

Question 52

Directed walk

Answer 52

Finite alternating sequence of vertices and arcs from v1 to vn (and the arcs in between them)

Question 53

Semi walk

Answer 53

Finite alternating sequence of vertices and arcs (can travel in any direction on arcs)

Question 54

Strongly connected

Answer 54

For all vertex pairs, there exists a path from 1 vertext to the other and visa versa (every vertex has an in degree of at least 1}

Question 55

Weakly connected

Answer 55

For every vertexr pair, there is at least 1 path between them (the underlying graph is connected)

Question 56

Disconnected graph

Answer 56

Different components

Question 57

R-regular digraph

Answer 57

Out degree = in degree, for every vertex in the graph

Question 58

Symmetric

Answer 58

Arc in 1 direction implies arc in the other direction

Question 59

Asymmetric

Answer 59

Between each vertex there is only one arc (1 direction between each arc)

Question 60

Tournament

Answer 60

Every pair of vertices in an asymmetric digraph are joined by exactly one arc

Question 61

Directed tree

Answer 61

Asymmetric digraph whose underlying graph is a tree

Question 62

Directed rooted tree

Answer 62

Exactly 1 vertex r, root of T, such that there exists a r-v path in T for every vertex of T

Question 63

Size of a k(mxn) graph

Answer 63

(mnC2)-m(nC2)

Question 64

Path length

Answer 64

Sum of weights of the edges travelled

Question 65

Distance

Answer 65

Minimum sum of weights between 2 vertices

Question 66

Origin/source

Answer 66

Where you start

Question 67

Endpoint / destination

Answer 67

Where you end