D1: Graph Theory + Definitions

studied byStudied by 8 people
0.0(0)
Get a hint
Hint

graph

1 / 40

41 Terms

1

graph

a mathematical model that consists of arcs/edges and nodes/vertices

New cards
2

network

a weighted graph i.e. a graph with numbers associated to its edges

New cards
3

vertex set

list of all the vertices in a given graph

New cards
4

edge set

a list of all the edges in a given graph

New cards
5

subgraph

A part of the original graph (vertices and edges also belong to original graph)

New cards
6

degree/valency/order of a vertex

number of edges incident to it

New cards
7

pendant

a node of degree one

New cards
8

isolated

a node of degree zero

New cards
9

walk

a route through a graph along edges from one vertex to the next

New cards
10

path

a walk with no repeated vertices

New cards
11

trail

a walk with no repeated edges

New cards
12

cycle

a walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once (or a trail that starts and ends at the same vertex)

New cards
13

Hamiltonian cycle

A cycle that visits every vertex of a graph

New cards
14

two vertices are connected if...

...there is a path between them

New cards
15

a graph is connected if...

...all its vertices are connected

New cards
16

connected components

subgraphs that are connected

New cards
17

loop

an edge that starts and finishes at the same vertex

New cards
18

how does a loop affect the degree of a vertex

the vertex the loop originates from has a degree of 2 and not 1 due to it. this is because the loop is incident at the vertex twice.

New cards
19

simple graph

a graph with no loops or multiple edges between vertices

<p>a graph with no loops or multiple edges between vertices</p>
New cards
20

directed graph (digraph)

a graph with a direction associated with the edges

New cards
21

Euler's handshaking lemma

in any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges. As a consequence, the sum of the degrees must always be even.

<p>in any undirected graph, the sum of the degrees of the vertices is equal to 2x the number of edges. As a consequence, the sum of the degrees must always be even.</p>
New cards
22

how is euler's handshaking lemma used?

to determine whether a graph can exist - if the sum of the degrees is odd, that implies the number of edges is not an integer which is impossible

New cards
23

in any undirected graph there must be...

an even amount of vertices with an odd degree

<p>an even amount of vertices with an odd degree</p>
New cards
24

tree

a simple connected graph with no loops or circuits

New cards
25

spanning tree

a tree which includes all the vertices of the graph

New cards
26

complete graph

a graph where every vertex is directly connected by a single edge to each and every other vertex

New cards
27

how is a complete graph denoted?

Kₙ where n is the number of vertices in the graph

New cards
28

isomorphic graphs

graphs that show the same information but are drawn differently

New cards
29

what makes two graphs isomorphic?

- they have the same number of vertices with the same degree

- the vertices are connected in the same way

- the vertices may have different labels as they are not the same graph but still an equivalence

New cards
30

adjacency matrix

a matrix that provides information about the connections between the vertices in a graph

New cards
31

what should each entry be for the adjacency matrix of an unweighted graph?

the number of arcs joining two points

New cards
32

describe how a loop from point A to A is depicted in an adjacency matrix for an undirected graph

it counts as two arcs as they can go in either direction ∴ the entry would be 2

(it is a similar principle to how e.g. AB could be 1 ∴ BA would also be 1)

New cards
33

distance matrix

the matrix associated with a weighted graph

New cards
34

what should each entry be for a distance matrix?

the weight of the arc joining two nodes

New cards
35

what if there are multiple arcs joining two vertices in a weighted graph? what should the entry be in the distance matrix + why?

the smallest weight; this is because when an algorithm is applied to the matrix to e.g. find the shortest route, the least value is desired.

New cards
36

minimum spanning tree (MST)

a spanning tree such that the total length of its edges is as small as possible

New cards
37

what is another name for a minimum spanning tree?

minimum connector

New cards
38

Eulerian circuit

A trail that starts and ends at the same vertex and traverse every arc no more than once

New cards
39

Semi-eulerian circuit

A trail that traverses every arc no more than once, but doesn’t start and end at the same vertex

New cards
40

Traits of a Eulerian graph

  • all vertices are even

  • connected

  • contains a Eulerian circuit

New cards
41

Traits of a semi-Eulerian graph

  • exactly two vertices are odd

  • connected

  • contains a semi-Eulerian circuit

New cards

Explore top notes

note Note
studied byStudied by 58 people
... ago
5.0(3)
note Note
studied byStudied by 24 people
... ago
5.0(1)
note Note
studied byStudied by 21 people
... ago
5.0(1)
note Note
studied byStudied by 61 people
... ago
5.0(3)
note Note
studied byStudied by 8 people
... ago
4.0(1)
note Note
studied byStudied by 7 people
... ago
5.0(1)
note Note
studied byStudied by 19 people
... ago
5.0(1)
note Note
studied byStudied by 24 people
... ago
5.0(1)

Explore top flashcards

flashcards Flashcard (27)
studied byStudied by 2 people
... ago
5.0(1)
flashcards Flashcard (403)
studied byStudied by 11 people
... ago
4.0(1)
flashcards Flashcard (104)
studied byStudied by 17 people
... ago
5.0(2)
flashcards Flashcard (33)
studied byStudied by 6 people
... ago
5.0(1)
flashcards Flashcard (210)
studied byStudied by 21 people
... ago
5.0(1)
flashcards Flashcard (46)
studied byStudied by 5 people
... ago
5.0(1)
flashcards Flashcard (69)
studied byStudied by 35 people
... ago
5.0(1)
flashcards Flashcard (98)
studied byStudied by 22 people
... ago
5.0(1)
robot