Graph theory and applications to real world problems
EDG701 Graph theory and applications to real world problems
Graph is a discrete structure used to represent relationships between entities. The entities in a graph correspond to dots or vertices and can represent, for example, individuals, states, geographic points, structural parts, etc. Associated entities are linked with a line called edge; for example, there is an edge between people who are friends, allied states, cities connected via a highway, adjacent sites in an excavation, and so on.
Graph theory is a powerful tool for formulating problems, making them precise, and defining fundamental interrelationships. Graphs have very wide-ranging applicability and it is possible in graph theory to bring a previously unfamiliar scientist to the frontiers of research rather quickly. Sometimes, simply formulating a problem precisely helps us to understand it better. Also, often, formulation of the problem precisely is enough to give us insight on why the problem is hard.
In the context of this course, we examine basic categories of graphs and their properties and study, at an elementary level, typical graph-theoretic problems (like coloring, independent set, set cover, shortest path, etc.) with wide practical applications and special interest in the study of issues in the area of history-archaeology.
The course contributes to the development of “computational thinking” and offers the necessary background for the exploitation and use of methods, techniques and tools from the area of computer science and technology in the study of issues in the field of modern history-archaeology.
Companions
- DISCRETE MATHEMATICS AND ITS APPLICATIONS, K. Rosen (Eudoxus code: 77106820)
- ALGORITHMS TO LIVE BY. THE COMPUTER SCIENCE OF HUMAN DECISIONS, B. Christian, T. Griffiths (Eudoxus code: 86193640)