CHP 2: Graphs and Networks - Key Terminology Flashcards

1
Q

Definition of GRAPH

A

A graph consists of points (called vertices or nodes) which are connected by lines (edges or arcs).

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

Definition of WEIGHTED GRAPH

A

When a graph has a number associated with each edge (usually called its weight).
Also called weighted network.

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

Definition of SUBGRAPH

A

A graph, each of whose vertices belongs to the original graph and each of whose edges belongs to the original graph. (Part of the original graph)

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

What is a list of vertices often called?

A

Vertex Set

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

What is a list of edges often called?

A

Edge Set

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

Definition of DEGREE

A

Number of edges incident to a vertex. If even it is called an even degree and vice versa for odd.

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

Definition of VALENCY

A

Number of edges incident to a vertex. If even it is called an even degree and vice versa for odd.

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

Definition of ORDER OF A VERTEX

A

Number of edges incident to a vertex. If even it is called an even degree and vice versa for odd.

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

Definition of WALK

A

A walk is a route through a graph along edges from one vertex to the next.

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

Definition of PATH

A

A path is a walk in which no vertex is visited more than once.

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

Definition of CYCLE

A

A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.

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

Definition of HAMILTONIAN CYCLE

A

A cycle that includes every vertex.

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

Definition of CONNECTED GRAPH

A

When all vertices are connected by paths.

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

Definition of LOOP

A

A loop is an edge that starts and finishes at the same vertex.

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

Definition of SIMPLE GRAPH

A

A graph in which there are no loops and there is at most one edge connecting any pair of vertices.

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

Definition of DIRECTED EDGE

A

If edge of graph have a direction associated with them they are a directed edge.

17
Q

Definition of DIGRAPH

A

Abbreviation of directed graph and means a graph with directed edges.

18
Q

Define EULER’S HANDSHAKING LEMMA

A

In any undirected graph, the sum of the degrees of the vertices is equal to 2 x the number of edges. As a consequence, the number of odd vertices must be even, including possibly zero.

19
Q

Definition of TREE

A

A connected graph with no cycles.

20
Q

Definition of SPANNING TREE

A

A subgraph which includes all the vertices of the original graph and is also a tree.

21
Q

Definition of COMPLETE GRAPH

A

A graph in which every vertex is directly connected by a single edge to each of the other vertices.

22
Q

Definition of ISOMORPHIC GRAPH

A

A graph which show the same information but may be drawn differently.

23
Q

Definition of ADJACENCY MATRIX

A

Can be used to represent a graph or network and provides information about the connections between the vertices in a graph.
Each entry describes the number of arcs joining the corresponding vertices.

24
Q

Definition of DISTANCE MATRIX

A

A matrix associated with a weighted graph.

its entries represent the weight of each arc, not the number of arcs.