Introduction to Graphs Flashcards
Definition of Graph
Collection of vertices and edges. Each edge is said to join two vertices, which are called its end points.
Informally: Set of vertices (nodes) and set of edges (arrows) which connect pairs of vertices.
Types of graphs
- Undirected graph (arrows in both directions have the same value)
- Directed graph (arrows in each direction have different values)
- Mixed graph
Explain Weighted graph and weighted matrix
Weighted graph: There are values on the edges
Weighted matrix: show on a matrix the values on edges between nodes. In case nodes aren’t connected to each other or we are travelling directly from a node to the same node the value is infinity.
Simple or strict graph
Nonsimple graph is when there is more than one edge between any two different vertices (nodes) or there are loops around a single vertex (node)
Connected or disconnected graph
In a connected graph each vertex (node) is reachable so there is a path between every pair of vertices (nodes).
A graph with just one vertex is connected
Complete graph
You can travel to each vertex (node) from any other vertex (node). Everything is connected to everything else.
A graph in which all vertices are mutually connected by means of direct edges.
Cycle graph
Simple connected graph where each vertex is connected with two other vertices
Eulerian path and Eulerian cycle
Eulerian path: a trail in a connected graph in which we can visit every edge exactly once
Eulerian cycle: is an Eulerian path which starts and ends on the same vertex.
Hamiltonian path and Hamiltonian cycle
Hamiltonian path: a trail in a connected graph in which we can visit every vertex exactly once
Hamiltonian cycle: a path that visits all the graph’s vertices exactly once before returning to the starting vertex for this graph.
Eulerian path vs Hamiltonian path
Eulerian: edges
Hamiltonian: vertices (nodes)
