Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Ops Res > Graph Theoey > Flashcards

Graph Theoey Flashcards

Basic definitions

1
Q

Simple graph

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Order

A

Number of vertices, p

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Size

A

Number of edges, q

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Density

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Multigraph

A

More than 1 edge between vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Pseudograph

A

Contains a loop

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Open neighbourhood

A

All vertices surrounding a vertex Ng(v)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Closed Neighbourhood

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Incident

A

Edge and vertex are touching

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Degree

A

DegG(Vi) number of vertices adjacent to vertex i

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Isolated vertex

A

Degree 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

End vertex

A

Degree 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Even vertex

A

Even degree, include isolated vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Minimum degree

A

Lowest degree of a vertex small delta

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Maximum degree

A

Maximum degree of a vertex big delta

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Fundamental thm of graph theory (thm 2.1)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Corollary of 2.1

A

Every graph has an even number of odd vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Subgraph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Propper subgraph

A

Can’t be exactly the same

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Spanning subgraph

A

Vertices exactly the same, but not all edges

are there

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Edge induced subgraph

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Walk

A

Finite alternating sequence of vertices and edges from v1 to vn

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Path

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Distance

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Cycle

A

Path where you end where you started

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Acyclic graph

A

Graph with no cycles

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Trail

A

No repeates edges (vertices don’t matter)

28
Q

Circuit

A

Trail that closes

29
Q

Connected graph

A

There is a path between every vertex in the graph

30
Q

Disconnected graph

A

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

31
Q

Component

A

“seperate bits”

32
Q

Bridge

A

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

33
Q

Cut vertex

A

Vertex which, if removed, increases the number of components

34
Q

R-regular

A

All vertices have degree r

35
Q

Complete graph of order n

A

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

36
Q

Partite set

A

No edges between vertices in set

37
Q

Complete multipartite graph

A

Complete graph within partite sets

38
Q

Planar graph

A

Graph that can be drawn with no edges crossing

39
Q

Plane graph

A

Graph that is drawn with no edges crossing

40
Q

Kuratowski’s thm

A

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

41
Q

Nonplanar graph

A

Can’t be drawn without edges crossing

42
Q

Tree

A

Acyclic connected graph, order n implies size n-1

43
Q

Spanning tree

A

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

44
Q

Adjacency matrix

A

Represents graph: 1 for edge 0 for no edge

Use capital letter: A(G2) =…

45
Q

Directed graph

A

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)

46
Q

Out-neighbourhood

A

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

47
Q

In neighbourhood

A

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

48
Q

Out degree

A

Cardibality of out neighbourhood of vertex

49
Q

In degree

A

Cardinality of in neighbourhood of vertex

50
Q

Degree of vertex in directed graph

A

degD(v) = odD(v) + idD(v)

out degree of D(v) + in degree of D(v)

51
Q

Ist theorem of digraph

A

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

52
Q

Directed walk

A

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

53
Q

Semi walk

A

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

54
Q

Strongly connected

A

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}

55
Q

Weakly connected

A

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

56
Q

Disconnected graph

A

Different components

57
Q

R-regular digraph

A

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

58
Q

Symmetric

A

Arc in 1 direction implies arc in the other direction

59
Q

Asymmetric

A

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

60
Q

Tournament

A

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

61
Q

Directed tree

A

Asymmetric digraph whose underlying graph is a tree

62
Q

Directed rooted tree

A

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

63
Q

Size of a k(mxn) graph

A

(mnC2)-m(nC2)

64
Q

Path length

A

Sum of weights of the edges travelled

65
Q

Distance

A

Minimum sum of weights between 2 vertices

66
Q

Origin/source

A

Where you start

67
Q

Endpoint / destination

A

Where you end

Ops Res (4 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions