Graph Theory | Arman Boyaci

Posts Tagged ‘Graph Theory’

A matlab implementation of Havel-Hakimi algorithm

Saturday, June 11th, 2011

In graph theory, degree of a given vertex is the number of vertices which are neighbour to this vertex. Let $(d_0, d_1, \ldots , d_n)$ be a degree sequence then we can check whether it is possible to construct a graph such that the degrees of vertices follows this degree sequence. We call such a degree sequence graphical. The first simple check is to sum all the degree values. This number should even by hand-shakking lemma. This is a necessary condition but not sufficient. For example it is impossible to construct a graph with a degree sequence [3 3 3 1].

Erdős–Gallai theorem gives us necessary and sufficient conditions for this problem.

the sum of the sequence is even and
$\sum_{i=1}^{k}d_i \leq k(k-1) + \sum_{i=k+1}^n \min(d_i,k) \quad \text{for } k \in \{1,\dots,n\}$

Suppose the degree sequence is graphical then the following simple procedure construct a possible graph implementation from this given degree sequence.

Pseudocode: Havel-Hakimi

Begin with no edges
Start residual degree requirement values with the given degree sequence
While residual degree requirement of some vertex is non-zero

Sort vertices in non-increasing order of residual degree requirement $rd_1, rd_2, \ldots rd_n$
Make an edge between first vertex and the next $rd_1$ vertices in the previous list
Update residual degree requirements

Matlab Code: Havel-Hakimi

function E = mcmc_graph(degree_sequence)

n = size(degree_sequence,2);
% Check if the given degree sequence is graphical
degree_sequence_feasible = 1;
if mod(sum(degree_sequence),2)
    degree_sequence_feasible = 0;
else
    sorted_degree_sequence = sort(degree_sequence,'descend');
    for k=1:n
        temp_sum = 0;
        for i=k+1:n
            temp_sum = temp_sum + min(sorted_degree_sequence(i),k);
        end
        if (sum( sorted_degree_sequence(1:k)) > k*(k-1) + temp_sum )
            degree_sequence_feasible = 0;
        end
    end
end

m = sum(degree_sequence)/2;
E = zeros(m,2);

% Construct an initial graph with Havel-Hakini
if degree_sequence_feasible
    ds = degree_sequence;
    i = 0;
    while sum(ds) > 0
        [residual_degree vertices] = sort(ds,'descend');
        selected_vertices = vertices(2:residual_degree(1)+1);
        E(i+1:i+residual_degree(1),:) = ...
            [repmat(vertices(1),residual_degree(1)) selected_vertices'];
        i = i + residual_degree(1);
        ds(vertices(1)) = ds(vertices(1)) - residual_degree(1);
        ds(selected_vertices) = ds(selected_vertices) - 1;
    end

Tags: Graph Theory, Matlab
Posted in General | No Comments »

Path Cover

Friday, June 18th, 2010

A path cover is a set of paths that cover all vertices. Minimum cardinality path cover problem is NP-hard for general graph classes, however it can be solved in polynomial time for some special cases.

Given any acyclic directed graph a minimum path cover of G can be obtained by finding a maximum matching in a properly constructed bipartite graph.

Let’s see on an application.

A transportation problem

A company wants to organize some transports between given locations. Each transport has a specific departure time. The same vehicle can be used for two transports i and j if the following are satisfied:
(1) arrival location of i and departure location of j are the same
(2) arrival time of i is earlier then the departure time of j

The objective is to find the minimum number of vehicles necessary to ensure all the transports.

Solution method

Let us define a bipartite graph G = (U,V,E) where vertex sets U and V represent locations. We put an edge between two vertices u_i and v_j if the transport j can be done by the same vehicle after transport i.

The minimum number of vehicles to make all transports is equal to n-M where M is the size of a maximum matching. Each edge in the matching indicates that the corresponding transports can be done one after the other by the same vehicle. Paths in the cover are obtained by following the edges of the matching and every unmatched vertex corresponds to the end of a path.

An example

	v1	v2	v3	v4
v1	0	2	4	1
v2	-	0	3	3
v3	-	-	0	2
v4	-	-	-	0

transport	departure	arrival	departure time
t1	v1	v2	6pm
t2	v1	v4	3pm
t3	v2	v4	3pm
t4	v2	v3	12pm
t5	v3	v2	16pm
t6	v4	v2	11pm
t7	v4	v3	9pm

Company's transportations

Corresponding bipartite graph and the maximum matching

According to this matching transports (t1,t4,t5) can be done with a single vehicle as well as (t2,t6) and (t3,t7). Therefore the company needs 3 vehicles.

Solution of the path cover problem

Tags: application, Graph Theory
Posted in Optimization | No Comments »

Unit Disk Graphs

Tuesday, February 9th, 2010

A Disk Graph is an intersection of set of disks in the Euclidean plane. They are mostly used to model telecommunications systems. We assume that each transmitter/receiver has a circle of certain diamater area of effect. Disk graphs are one of the well studied class of graphs in the literature. For different graph theoretical problems(stable set, vertex coloring, clique) results are available in the literature. Most of the problems are NP-hard. In my report, I am mainly focused on approximation algorithms for disk graphs. There exist also a presentation file created by using Latex/Beamer.

Tags: Approximation Algorithms, Beamer, Graph Theory
Posted in Optimization | No Comments »

Logo

a science blog