Graph Theory and Networks
Over the course of eight days, we have worked vigorously on solving and understanding Graph theory. Graph theory is the use of lines(edges) and points(vertices) to model real situations and/or objects.
Understanding Graph Theory
However, to understand graph theory there are many things to learn. First, you should know that there are many different types of graphs used in graph theory including null graphs, trivial graphs, simple graphs, undirected graphs, directed graphs, complete graphs, connected graphs, disconnected graphs, cyclic graphs, and many more. Second, you need to understand the different attributes of the graphs; Graphs can be different shapes. They are connected through edges and vertices, and can be disconnected or connected These graphs can also be Euler circuits, and Euler paths, or none.
Graph Theory Represented in Real Life
Graph theory is seen in many different ways in life. An example that we observed and learned about was painting lockers. The locker situation used a vertex edge graph. The main goal was to paint all of the lockers in the shortest amount of time. The lockers were aligned across each other and some were double-sided. This was the first example we explored representing a vertex edge graph. A vertex edge graph is a graph consisting of points (vertices) and arcs or line segments (edges) connecting all the points as shown above.
Social media is in every aspect of our lives. Whether it is for contacting friends or posting pictures, people use it every day. Though we might not know, social media is also a type of graph. They are classified as Star Graphs. These Star Graphs represent one video/meme that can stem off into multiple other videos and websites.
A star graph is a complete bipartite graph in which n-1 vertices have degree 1 and a single vertex has a degree (n -1). A complete bipartite graph is a graph in which each vertex in the first set is joined to each vertex in the second set by exactly one edge.
Similar to social media, social science can also be represented by graphs. These graphs are called directed graphs. Things like rumors can spread from one person to another repeatedly. A directed graph is a graph in which the edges are directed by arrows as shown by the image on the left.
Just like the painting lockers problem in the introduction, Google Maps are also a part of graph theory. Map direction represents Multi Graphs because rivers and roads connect and spread through different areas.
A Multi-Graph is a graph in which there are multiple edges between any pair of vertices or there are edges from a vertex to itself. Networks are like paths that are represented by the graphs mentioned above.
A Type of Graph We Indepthly Explored:
Euler Circuits and Paths
To further understand this you have to know what an Euler circuit is. An Euler circuit is used to find the best path. This means that you have to get around the graph and back without crossing over the same line more than once.
Their properties are used to solve problems about optimum circuits. An Euler circuit is present when each vertex has an even number of edges coming out of it and when the graphs touch by their points instead of their edges. An Euler circuit is not present when the shapes are connected by edges and when the degree of the vertices is odd. An Euler path is a path on the graph's edge that only goes across each edge once and also starts and ends on different vertices.
Graphs can have an Euler circuit or Path but they can also have neither. Due to this, not all Graph theories can be used to represent all situations. Graphs with Euler Paths can show directions from one place to another while Euler circuits can show a walk where you would start and end at the same point. Euler Paths and Circuits can sometimes be used for the same situation depending on the person. If a person is painting lockers they could choose which path to take and which lockers to paint. That decision alone would be Euler Path. But they wanted to start at a specific location, and come back there after all the lockers are painted, they would need a Euler Circuit.