7.02 | graph theory

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/29

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

30 Terms

1
New cards

what is a graph?

a set of vertices connected by arcs.

2
New cards

what is a vertex/node?

a point in the graph.

3
New cards

what is an arc/edge?

a line or curve with a vertex at each end.

4
New cards

what does it mean for two vertices to be adjacent?

if there is an arc with these vertices at its ends.

5
New cards

what is a loop?

an arc that directly connects to itself.

6
New cards

what is an indirect connection between two vertices?

passes through other vertices and involves more than one arc.

7
New cards

what defines a simply connected graph?

both simple (exactly one arc between any two adjacent vertices and no loops) and connected (possible to get from any vertex to any other).

8
New cards

what is the degree of a vertex?

the number of arcs incident on that vertex.

9
New cards

what is the relationship between the sum of vertex degrees and the number of arcs in a graph?

the sum of the vertex degrees is twice the number of arcs.

10
New cards

what is a tree?

a simply connected graph with the minimum possible number of arcs.

11
New cards

what is a subgraph?

formed using some of the arcs of the graph together with the vertices that these arcs connect, and possibly some other unconnected vertices.

12
New cards

what is a walk?

a connected subgraph consisting of a set of arcs where the end vertex of one arc is the start vertex of the next.

13
New cards

what is the difference between a trail and a walk?

a walk can repeat edges, whereas a trail must have distinct edges (cannot be repeated).

14
New cards

what is a path?

a trail in which no vertex is repeated.

15
New cards

what is a cycle?

a closed path, meaning it has an extra arc that joins the end vertex back to the start vertex.

16
New cards

what is a complete graph?

a simply connected graph with the maximum possible number of arcs.

17
New cards

what is a bipartite graph?

a graph where its vertices can be partitioned into two sets so that every arc joins a vertex from one set to a vertex in the other set.

18
New cards

what is a complete bipartite graph?

a simply connected bipartite graph with the maximum possible number of arcs.

19
New cards

what characterises an eulerian graph?

no odd vertex degrees and is traversable with the same start and finish point.

20
New cards

what is a semi-eulerian graph?

has exactly two odd vertex degrees and is semi-traversable.

21
New cards

what defines a hamiltonian graph?

it contains a cycle that passes through every vertex exactly once, apart from the start and finish being the same.

22
New cards

what does ore's theorem state?

for a simply connected graph, if the sum of the vertex degrees for every pair of non-adjacent vertices is at least the number of vertices, then the graph is hamiltonian.

23
New cards

what is a digraph?

a graph with directed arcs.

24
New cards

what is euler's relation for planar graphs?

for any planar graph, the relation states that V - E + F = 2, where V is the number of vertices, E is the number of edges, and F is the number of faces.

25
New cards

what is an adjacency matrix?

it shows the number of arcs that directly join pairs of vertices.

26
New cards

what is a network?

a weighted graph, meaning that the arcs have numerical values attached to them.

27
New cards

what is a planar graph?

any graph that can be drawn with no arcs crossing (can be drawn as one layer).

28
New cards

what is a subdivision?

inserting a vertex of degree 2 into an arc.

29
New cards

what is a contraction?

removing an arc from a graph and merging the two vertices that it previously joined.

30
New cards

what is kuratowski’s theorem?

a necessary and sufficient condition for a finite graph to be planar is that it does not contain a subgraph that is a subdivision of K5 or K3,3