# Chapter 2 Graphs and Networks Flashcards

What is a graph?

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

What is a graph where each edge has a numbers associated with it called?

Weighted graph or a Network

What is a weighted graph/network?

A graph withy numbers associated with each edge

In a weighted graph, what are the numbers usually called?

Its weight

What is a vertex?

A point in the graph

What are vertices sometimes called?

Nodes

What is an edge?

A line segment joining vertices

What is the other word for edge?

Arc

What do you need to be careful about with networks?

They aren’t usually drawn to scale

As a result the shortest path may not be the obvious path

That is the list of vertices called?

Vertex set

What is the list of edges called?

The edge set

What is the vertex set?

The list of vertices

What is the edge set?

The list of edges

What is a subgraph?

A subgraph is part of the original graph

When is a vertex and an edge incident?

If they are connected

What is the degree of a vertex?

The number of edges incident to a particular vertex

What are the other ways to say degree of a vertex?

Valency of a vertex

Order of a vertex

What does even degree mean?

The vertex has an even number of incident edges

The degree of vertex will be an even number

What deos odd degree mean?

The vertex has an odd number of incident edges

The degree of vertex will be an odd number

What phrase can be used to say: The vertex has an even number of incident edges?

Even degree

What phrase can be used to say: The vertex has an odd number of incident edges?

Odd degree

What is a walk?

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

What is a path?

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

What is a trail?

A trail is a walk in which no edge is visited more than once