Group Project

Phase $1$

DM$857$ Introduction to Programming

DS$830$ Introduction to Programming

Minimal frustration of a random graph

During this project, you will implement a program to define a connected random graph, evaluate a

metric $($a function that returns a number as an outcome$)$ over the graph and minimize such a metric.

A random graph consists of a set of sites connected among them by edges, without any regular pattern.

Each site must be connected at least to another site, as such a graph is uniquely identified by its

edges. For example the list of edges:

$(1,2)$

$(2,8)$

$(8,1)$

$(1,12)$

identifies the graph reported in Fig. $1.$

Each site can be coloured with a colour identified by a float number in $0,1.$ Because of the time

Figure $1$: Example graph

constraints connected to phase $1$ of the project, we will simplify the process and consider only two

colours identified respectively by $0$ and $1.$

The project aims to find a colouring pattern that minimizes the "frustration" of the graph. With

frustration, we identify the preference of the sites of having a colour different from its connected Project Overview:

Objective:

Define a connected random graph, evaluate a metric related to graph coloring, and minimize this

metric.

Components:

Configuration: Setting up the parameters for the random graph.

Simulation: Running the program to evaluate the graph and minimize the associated metrics.

Reporting: Presenting the results of the simulation.