Notes

In Mathematics and Computer Science, an algorithm is a finite sequence of well defined, computer implementable instructions, typically to solve a class of problems or to perform a computation.

Algorithms are the ideas behind computer programs, this procedure can be written in many different languages producing the same result. We will see theoretically with SUDO codes. Every algorithm has its own process time, and to solve a problem there can be many different algorithms with many different times of execution.

Graph Theory, it is the language used to describe problems solved by algorithms. In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically.

In Computer Science, graphs are used to represent networks of communication, data organization, computational devices, the flow of computation. For instance, the link structure of a website can be represented by a directed graph, in which the vertices represent web pages and directed edges represent links from on page to another. A similar approach can be taken to problems in social media, biology, computer chip design, mapping the progression of neuro-degenerative diseases, and many other fields. The development of algorithms to handle graphs is therefore of major interest in computer science.

The paper written by Leonhard Euler on the "Seven bridges of Konigsberg" and published in 1736 is regarded as the first paper in the history of graph theory. From Euler takes the name a class of graphs which are the Eulerian Graphs, this term has two common meanings in graph theory. One meaning is a graph with a Eulerian Circuit, and the other is a graph with every vertex of even degree. These definitions coincide for connected graphs.

What is defined as Euler's theorem is the concept that a connected graph has an Eulerian cycle if and only if every vertex has even degree, where an Eulerian cycle is a path in a finite graph that visits every edge exactly once (allowing for revisiting vertices).

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets X and Y such that every edge connects a vertex in X to one in Y. One of the most common algorithms is the Matching problem, a perfect matching occurs when nobody remains without match and also in case of preferences, the highest degree of preferences are matched.

Many problems and theorems in graph theory have to do with various ways of colouring graphs. Typically, one is interested in coloring a graph so that no adjacent vertices have the same color, or with other similar restrictions. One may also consider edges (possibly so that no two coincident edges are the same color), or other variations.

The problem of Proper Coloring a graph states that a color is "proper" if and only if an edge exists such that the color of a vertex A is different from the color of a vertex B, connected by an edge. The Chromatic Number X(G) is the minimum number of colors in a proper coloring. Regarding this, exists the Four Color Theorem which states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color.

A Subgraph G' of a graph G is a graph G' whose vertex set, and edge set are subsets of those of G. If G' is a subgraph of G, then G is said to be a supergraph of G'.

A lot of problems in computer science consist of finding a subgraph with certain special properties.

A spanning subgraph is defined by the fact that the vertex set of the subgraph (V') is equal to the vertex set of supergraph (V).

An Induced Subgraph of a graph is another graph, formed from a subset of the vertices of the graph and all of the edges connecting pairs of vertices in that subset. Or the contrary, when from a subset of the edges of a graph a new graph is obtained defining the missing vertices.

Isomorphism in subgraphs, G1 and G2 are isomorphic if there exist a bijection f: V1 -> V2 such that for each edge in G1, applying a relabeling, you find an edge in G2. Defining an algorithm capable of finding this bijection function was considered an intractable problem.

A Complete Graph is composed of n vertices and a set of edges such that every vertex is connected to all the others.

The Vertex Degree is the number of edges incidents with that vertex.

In graph theory, the degree of a vertex of a graph is the number of edges that are incident to the vertex, and in a multigraph, loops are counted twice. The degree of a vertex v is denoted **deg(v) **or degv. The maximum degree of a graph G, denoted by Δ(G), and the minimum degree of a graph G, denoted by δ(G), are the maximum and minimum degree of its vertices.

An Incidence Matrix, M (V, E) where we introduce 1 if a vertex € to the edge, and 0 otherwise. From this matrix we are able to see that every column has two 1s, indicating that every edge is connected to two vertices. Instead, if we sum up the rows, we get the degree of the correspondent node.

In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related (called incident in this context) and 0 if they are not.

An Adjacency Matrix, A (V, V). We introduce a 1 in the matrix If two vertices are adjacent, and a 0 otherwise. This matrix tells us whether two vertices are connected.

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix is a (0,1)-matrix with zeros on its diagonal. If the graph is undirected, the adjacency matrix is symmetric.

A sequence of vertices W = (V1, ..., Vk) is a Walk in G if (Vi, Vi+1) € E for 1 <= i <= k. A **Walk **is **Closed ** if V1 = Vk.  A **Path **is a walk in which the vertices are distinct.  A **Cycle **is a closed walk in which the vertices are distinct except for V1 and Vk.  A **Tree **is a graph which is **Connected **and has **No Cycles **(Acyclic).

1Bocconi/Bocconi - Fundamentals of Computer Science/Images - Bocconi Fundamentals of Computer Science/image3.png

In graph theory, a component, sometimes called a connected component, of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. An alternative way to define components involves the equivalence classes of an equivalence relation that is defined on the vertices of the graph. In an undirected graph, a vertex v is reachable from a vertex u if there is a path from u to v. In this definition, a single vertex is counted as a path of length zero, and the same vertex may occur more than once within a path. Reachability is an equivalence relation, since:

• It is reflexive: There is a trivial path of length zero from any vertex to itself.
• It is symmetric: If there is a path from u to v, the same edges form a path from v to u.
• It is transitive: If there is a path from u to v and a path from v to w, the two paths may be concatenated together to form a path from u to w.

The components are then the induced subgraphs formed by the equivalence classes of this relation.

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.

It uses the opposite strategy as depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.