By Myla James, Shania Johnson, Maya Mukerjee, and Savitha Saminathan.

 

Graph Theory

Here’s some definitions to help you understand our assignment:

Nodes – vertex/point.
Edges – lines connecting vertices.
Adjacent – two nodes (vertices) are adjacent if they share an edge (line).
Degree – number of edges adjacent to a particular node.

We started this problem set with learning about the difference between connected and disconnected graphs.

Connected Graph – able to travel from one node to any other through its edges.
Disconnected graph – more complex; it has components.
Components – parts of the graphs that are connected.

Confused? Then here’s a diagram.
Triangle ABC and Triangle DEF are both components of graph ABFE.

 

As well as simple graphs, we learned about multi-graphs.

Multiple graphs – have multiple edges between the same pair of nodes.

Here’s another diagram:

Loops – an edge connecting a node to itself; loops add two to the degree of the graph.

Euler Paths and Euler Circuits.

We were given a map of the city of Königsberg, Prussia that helped us learn about paths and circuits. Euler Paths and Circuits were named after Leonhard Euler, who asked the question: “Is there some route in this city wherein one would cross each of the seven bridges one and only once?”

 

 

An Euler path must include two or less odd degree vertices.

We were also given a theorem:
In order for there to be an Euler path (in which each edge is traversed exactly once) in a graph, that graph must be connected and have two or less vertices of odd degree. If we restrict the path to circuits (in which the path must end at the same point at which it starts), the graph must have exactly zero vertices of odd degree in addition to being connected. Such a path is called an Euler circuit or Eulerian cycle.

In simplest form, an Euler path is a set of edges that is connected, and an Euler circuit is a set of edges that is connected and begins and ends at the same node. An analogy would be an electrical circuit. Electricity can flow in a closed circuit, but not an open path.

 

The most important thing to know is that Euler circuits are types of Euler paths.

 

Complete Graphs, Regular Graphs, and Hamilton Circuits/Paths.

 

Here are more definitions:

Complete graph – a graph where each node is adjacent to every other node in the graph. Complete graphs are always regular and always have Hamilton circuit/paths.
Regular graph – in regular graphs each vertex has the same degree; they may or may not be complete.
Hamilton paths – each vertex is visited once and only once.
Hamilton circuit – each vertex is visited once and only once and it starts and ends at the same node.
Permutation – rearrange the order of the nodes into all possible orderings.

 

Network Science using Python

Network Science involves quite a bit of programming most of which involves creating graphs on technological databases, and storing data and different information in those graphs.

Creating the graphs is complicated. We used different ways of coding and programming to make different types of graphs, whether they’re just simply lists or something more complicated like an actual graph. Sometimes, graphing itself can be considered rather stressful and even stress relieving.

We use the command print to finish a certain equation or something we’ve done to the graph. This shows us the result of our work. It was one of the first things we seemed to learn. Later on, we learned how to program addition, division, subtraction, and multiplication of graphs.

We learned how to use lists in the program known as Python. Which, honestly, is a simplistic way of coding. Python was already able to sort out certain things as long as you were able to put in the correct syntax for it to officially finish the code and output it all. Coding in Python honestly wasn’t too difficult, but it wasn’t simple either. It required focus and the ability to follow certain things in an acceptable way.