graphing and network terms

Question 1

Adjacency matrix

Answer 1

An adjacency matrix for a non-directed graph with vertices is a matrix in which the entry in rows and columns is the number of edges joining the vertices
i and j in an adjacency matrix, a loop is counted as 1 edge.

For a directed graph the entry in rows and columns is the number of directed edges (arcs) joining the vertex i and j in the direction i to j.

Question 2

Bipartite graph

Answer 2

A bipartite graph is a graph whose set of vertices can be split into two distinct groups in such a way that each edge of the graph joins a vertex in the first group to a vertex in the second group.

Question 3

Complete graph

Answer 3

A complete graph is a simple graph in which every vertex is joined to every other vertex by an edge. The complete graph with vertices is denoted . A complete bipartite graph is a bipartite graph where every vertex of the first set is connected to every vertex of the second set.

Question 4

Connected graph

Answer 4

A graph is connected if there is a path between each pair of vertices. A bridge is an edge in a connected graph that, if removed, leaves a graph disconnected.

Question 5

Cycle

Answer 5

A cycle is a closed walk which begins and ends at the same vertex and which has no repeated edges or vertices except the first. If , , and are the vertices of a graph, the closed walk that starts and ends at vertex (shown dotted) an example of a cycle.

Question 6

Degree of a vertex (graph)

Answer 6

In a graph, the degree of a vertex is the number of edges incident with the vertex, with loops counted twice. It is denoted deg .

In the graph below, deg =4, deg =2, deg =4 and deg =2.

Question 7

Directed graph

Answer 7

A directed graph is a diagram comprising points, called vertices, joined by directed lines called arcs. The directed graphs are commonly called digraphs.

Question 8

Eulers formula

Answer 8

For a connected planar graph, states that , where is the number vertices, is the number of edges and is the number of faces.

Question 9

Eulerian graph

Answer 9

A connected graph is Eulerian if it has a closed trail (starts and ends at the same vertex), that is, includes every edge and once only; such a trail is called an Eulerian trail. An Eulerian trail may include repeated vertices. A connected graph is

semi-Eulerian if there is an open trail that includes every edge once only.

Question 10

Face

Answer 10

The faces of a planar graph are the regions bounded by the edges, including the outer infinitely large region. The planar graph shown has four faces.

Question 11

Food web

Answer 11

A food web (or food chain) depicts feeding connections (who eats whom) in an ecological community.

Question 12

Graph

Answer 12

A graph is a diagram that consists of a set of points, called vertices, that are joined by a set of lines called edges. Each edge joins two vertices. A loop is an edge in a graph that joins a vertex in a graph to itself. Two vertices are adjacent if they are joined by an edge. Two or more edges which connect the same vertices are called multiple edges.

Question 13

Hamiltonian cycle

Answer 13

A Hamiltonian cycle is a cycle that includes each vertex in a graph (except the first), once only.

Question 14

Hamiltonian path

Answer 14

A Hamiltonian path is a path that includes every vertex in a graph once only.

A Hamilton path that begins and ends at the same vertex is a Hamiltonian cycle.

These concepts are useful in solving practical problems, such as: planning a sight-seeing tourist route around a city, or the travelling-salesman problem.

Question 15

Length (of a walk)

Answer 15

The length of a walk is the number of edges it includes.

Question 16

Network

Answer 16

The word network is frequently used in everyday life, for example, television network, rail network. Practical situations that the construction of a network can represent include trails connecting campsites in a National Park, a social network, a transport network with one-way streets, a food web, the results of a round-robin sporting competition.

Weighted graphs or digraphs can often be used to model such networks.

Question 17

Path (in a graph)

Answer 17

A path in a graph is a walk in which all of the edges and all the vertices are different. A path that starts and finishes at different vertices is said to be open, while a path that starts and finishes at the same vertex is said to be closed. A cycle is a closed path.

If and are the vertices of a graph, a walk from to along the dotted edges is a path. Depending on the graph, there may be multiple paths between the same two vertices, as is the case here.

Question 18

Planar graph

Answer 18

A planar graph is a graph that can be drawn in the plane. A planar graph can always be drawn so that no two edges cross.

Question 19

Simple graph

Answer 19

A simple graph has no loops or multiple edges.

Question 20

Subgraph

Answer 20

When the vertices and edges of a graph A (shown dotted) are also vertices and edges of the graph G , graph A is said to be a subgraph of graph G .

Question 21

Trail

Answer 21

A trail is a walk in which no edge is repeated.

Question 22

Walk (in a graph)

Answer 22

A walk in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A walk that starts and finishes at different vertices is said to be an open walk. A walk that starts and finishes at the same vertex is said to be closed walk.

If a, b, c and d are the vertices of a graph with edges ab, bc, cc, cd and bd then the sequence of edges (ab, bc, cc, cd ) constitute a walk. The route followed on this walk is shown dotted on the graph below.

This walk is denoted by the sequence of vertices abccd. The walk is open because it begins and finishes at different vertices.

A walk can include repeated vertices (as is the case above) or repeated edges. A example of a closed walk with both repeated edges, and hence vertices, is defined by the sequence of edges (ab, bd, bd, ba) and is denoted by the sequence of vertices abdba. The route followed is shown dotted in the graph below.

Depending on the graph, there may be multiple walks between the same two vertices, as is the case here.

Question 23

Weighted graph

Answer 23

A weighted graph is a graph in which each edge is labelled with a number used to represent some quantity associated with the edge. For example, if the vertices represent towns, the weights on the edges may represent the distances in kilometres between the towns.

Question 24

what is open

Answer 24

doesn’t start and end at the same location

Question 25

what is closed

Answer 25

starts and ends at the same place

Question 26

what is a trail

Answer 26

no repeat edges

Question 27

what is a path

Answer 27

a open graph that has no repeat vertices

Question 28

what is a cycle

Answer 28

a closed graph that has no repeat vertices

Answer 29

a graph

Question 30

what is the formula for finding the max edges if you are given the number of vertices

Answer 30

n(n-1)/2

Question 31

what is the formula for finding the min edges if you are given the number of vertices

Answer 31

n-1