SWEN2006 Lecture Graph Theory

Flashcards on Graph Theory based on lecture notes.

What are the different types of graphs?

Simple graphs, Multigraphs, Pseudographs, Directed graphs, Directed multigraphs

What is a Simple Graph?

A graph G = (V, E) consisting of V, a non-empty set of vertices and E, a set of unordered pairs of distinct elements of V called edges.

Give some application examples of Graph Models

Social networks, Transportation systems, Network topology, Biological systems, Knowledge Graphs

What is the degree of a vertex in an undirected graph?

The number of edges incident with it, except that a loop at a vertex contributes twice to the degree of the vertex.

What is an isolated vertex?

A vertex of degree 0.

What is a pendant vertex?

A vertex which has degree 1.

What is the Handshaking Theorem?

The sum of the degrees of the vertices is twice the number of edges.

What does Theorem 2 state about an undirected graph?

An undirected graph has an even number of vertices of odd degree.

What is the in-degree of a vertex v in a directed graph?

The number of edges with v as their terminal vertex.

What is the out-degree of a vertex v in a directed graph?

The number of edges with v as their initial vertex.

What does Theorem 3 state about a direct graph, G = (V,E)?

The sum of the in-degrees and the sum of the out-degrees are equal and both sums are the number of edges in the graph.

What is a Complete graph of n vertices, denoted Kn?

A simple graph that contains exactly one edge between each pair of distinct vertices.

How is a wheel Wn obtained?

Adding a vertex to the cycle Cn for n ≥ 3, and connecting this new vertex to each of the n vertices of Cn.

What is a Bipartite Graph?

A simple graph G in which its vertices V are partitioned into two disjoint sets V1 and V2 such that there is an edge between every vertex in V1 and a vertex in V2 (and no edge in G connects either two vertices in V1 or two vertices in V2).

What is a Complete Bipartite Graph?

Has its vertices partitioned in two disjoint sets m and n such that every vertex in m is connected to every vertex in n by an edge.

What is the theorem that determines if a simple graph is bipartite?

A simple graph is bipartite if and only if it is possible to assign one of two different colours to each vertex of the graph so that no two adjacent vertices are assigned the same colour.

What is a matching in a simple graph?

A subset of the set of edges of the graph such that no two edges are incident with the same vertex.

What is a maximum matching?

A matching with the largest number of edges.

What is a maximal matching?

A matching where all the vertices are matched.

What is Graph Colouring?

Assignment of a colour to each vertex of the graph so that no two adjacent vertices are the same colour.

What is the chromatic number of a graph?

The least number of colours needed for a colouring of that graph.

What is the adjacency matrix A of G?

The zero-one matrix with 1 as its (i, j)th entry when vi, vj are adjacent, and 0 as its (i, j)th when they are not adjacent.

What is a Path?

A sequence of edges that begins at a vertex of a graph and travels from vertex to vertex along edges of the graph.

What is a circuit?

Begins and ends at the same vertex, that is, if u = v, and has length greater than zero.

What is a simple path or circuit?

It does not contain the same edge more than once.

When is an undirected graph called connected?

There is a path between every pair of distinct vertices in the graph.

What is an Euler circuit in a graph G?

A simple circuit containing every edge of G.

What is an Euler path in a graph G?

A simple path containing every edge of G.

What is the requirement for a connected multigraph to have an Euler circuit?

Each of its vertices has even degree.

What is the requirement for a connected multigraph to have an Euler path but not an Euler circuit?

It has exactly two vertices of odd degree.

What is a Hamilton Path?

A simple path in a graph G that passes through every vertex exactly once.

What is a Hamilton circuit?

A simple circuit in a graph G that passes through every vertex exactly once

What can we find using Dijkstra’s Algorithm?

We can find the length of the shortest path between two vertices of a weighted graph.