Understanding Graphs in Mathematics and Computer Science
Graphs in mathematics and computer science are abstract data types used to represent relationships between objects. They consist of vertices connected by edges, which can be directed or undirected. Graphs find applications in various fields like electric circuits, networks, and transportation systems. Basic operations on graphs include adding vertices and edges. They can be represented using adjacency matrices, incidence matrices, or adjacency lists. Understanding concepts like adjacency and incidence is crucial for working with graphs effectively.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Definition A graph is an abstract data type that is meant to implement the undirected graph and directed graph concepts from mathematics. A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes or points, together with a set of unordered pairs of these vertices for an undirected graph or a set of ordered pairs for a directed graph. These pairs are known as edges, arcs, or lines for an undirected graph and as arrows, directed edges, directed arcs, or directed lines for a directed graph. The vertices may be part of the graph structure, or may be external entities represented by integer indices or references.
Definition A graph G = (V, E) is composed of: V: set of vertices E: set edges connecting the vertices in V An edge e=(u, v) is a pair of vertices V = {a,b,c,d,e} E = {(a,b), (a,c), (a,d), (b,e), (c,d), (c,e), (d,e)} a b c d e
Applications Electric circuits Networks Roads Flights Communications
Basic Operations Basic primary operations of a Graph Add Vertex Adds a vertex to the graph. Add Edge Adds an edge between the two vertices of the graph. Display Vertex Displays a vertex of the graph.
Graph Representations Graphs are represented using following representations: Adjacency Matrix Incidence Matrix Adjacency List
Adjacent and Incident If (v0, v1) is an edge in an undirected graph, v0 and v1 are adjacent The edge (v0, v1) is incident on vertices v0 and v1 If < v0, v1 > is an edge in a directed graph v0 is adjacent to v1, and v1 is adjacent from v0 The edge < v0, v1 > is incident on v0 and v1
Degree of Vertex The degree of a vertex is the number of edges incident to that vertex For directed graph, The in-degree of a vertex v is the number of edges that have v as the head The out-degree of a vertex v is the number of edges that have v as the tail If di is a degree of a vertex i in a graph G with n vertices and e edges, the number of edges is ? = ( ?=0 ? 1?? )/2
Path Sequence of vertices v1, v2, v3, vn such that consecutive vertices vi and vi+1 are adjacent simple path :no repeated vertices cycle path : simple path, except that the last vertex is the same as the first vertex a b c d e
Graph types connected graph : any two vertices are connected by some path sub graph : subset of vertices and edges forming a graph connected component : maximal connected subgraph tree : connected graph without cycles forest : collection of trees
Connectivity Let n = # of vertices and m = # of edges A complete graph one in which all pairs of vertices are adjacent Each of n vertices incident to n-1 edges, however each edge counted twice. Therefore m=n(n-1)/2 If a graph is not complete m<n(n-1)/2 If m<n-1 Graph is not connected
Directed vs. Undirected An undirected graph is one which the pair of vertices are not ordered, (v0, v1)=(v1,v0) A directed graph is one which each edge is a directed pair of vertices, < v0, v1 > != < v1, v0 >
Dijktras shortest path Algorithm
Dijktras algorithm between 2 nodes
Dijkstras algorithm based on Euclidean distance
