Graph Theory

    Published: September 02, 2018

    a short introduction to the creation and basic concepts of graph theory


    Graph Theory

    • 1. Graph Theory Graph Theory A Brief Look At History and basic concepts
    • 2. Origin Origin The medieval German city of Königsberg lay on both sides of the pregel river at the center were two large islands ,the two islands were connected to each other and to the river bank by 7 bridges . Carl Gottlieb Ehler a mathematician, grow obsessed by a riddle related to theses islands and bridges, which route would allow someone to cross all 7 bridges without passing the same bridge twice?
    • 3. Slide3 The answer is you can’t it’s not possible to pass all the 7 bridges without passing any of them twice, but attempting to explain why lead the famous mathematician Leonhard Euler to invent a new field in mathematics , the answer he came up with was related to a type of geometry that hasn’t existed yet a geometry he called the geometry of position now known as the graph theory . The reason that Euler came up with to why the riddle has no solution is that in order for the traveler to come into the island from one bridge and leave from a different one the number of bridges connected to each island must be even ,but both island have an odd number of bridges
    • 4. Fundamentals Fundamentals The most simple and least strict definition of a graph is the following: a graph is a set of points and lines connecting some pairs of the points Mathematicians name and number everything: in graph theory, points are called vertices, and lines are called edges
    • 5. Fundamentals Fundamentals •If two vertices are connected by an edge, then they are called adjacent, otherwise they are called disjoint •For a given vertex x, the number of all vertices adjacent to it is called degree of the vertex x, denoted by d(x) •Two edges are said to be adjacent if they have a vertex in common and disjoint otherwise •If a vertex x belongs to an edge e, then we say that they are incident to each other
    • 6. Graph Modeling Applications Graph Modeling Applications Graph theory has applications in countless fields of science specially computer science Mathematics: • the vertices are natural numbers from 1 to 100; two vertices are adjacent if the respective numbers have a common divisor different from 1; • vertices are computers in a network; two vertices are adjacent if the respective computers are linked together by telecommunications circuits; Genetics: • the vertices are fragments of a DNA sequence; two vertices are adjacent if the respective fragments overlap Chemistry: • the vertices are atoms in a molecule; two vertices are adjacent if the respective atoms have a bond; And so much more
    • 7. Graph Representations Graph Representations there are several special ways to store graphs in computer memory Adjacency lists: For every vertex x, form a list of all of its neighbors. The set of all such lists is called the adjacency list Adjacency matrix: It is a matrix (rectangular table from letters and/or numbers) which has one row and one column for each vertex. If vertex xi is adjacent to vertex xj, then (i, j)entry (element at the intersection of ith row and jth column) in the matrix is 1, otherwise it is 0.Infact,adjacency matrix is a square matrix. Incidence matrix: It is a matrix which has one row for each vertex and one column for each edge of a graph. If vertex xi is incident to edge ej , then the (i, j)-entry in the matrix is 1, otherwise it is 0.
    • 8. Basic Graph Classes Basic Graph Classes •Empty graphs: Any graph must have at least one vertex. In other words, we do not accept graphs without vertices. A graph may have no edges at all; such graphs are called empty. •Paths: A graph in which all vertices can be numbered (ordered from left to right) x1,x2, . . . , xn in such a way that there is precisely one edge connecting every two consecutive vertices and there are no other edges, is called a path. •Connected graphs: A graph is called connected if in it any two vertices are connected by some path; otherwise it is called disconnected.
    • 9. In conclusion In conclusion Graph theory is a very important and a very vast topic with applications spread across a plethora of fields and it all started from a simple riddle .