Day 07Part 02- Discrete- Parallel edge and Self loop , Simple graph , Multi graph , Pseudo graph.<\/p>\n
[fvplayer id=”171″]<\/p>\n
Graphs are fundamental structures in Discrete Mathematics<\/strong> and Computer Science<\/strong>, used to model relationships between objects. Let’s explore different types of graphs and their properties.<\/p>\n A graph<\/strong> G=(V,E)G = (V, E)<\/span>G<\/span>=<\/span><\/span>(<\/span>V<\/span>,<\/span>E<\/span>)<\/span><\/span><\/span><\/span> consists of:<\/p>\n V (Vertices or Nodes)<\/strong>: The set of points.<\/p>\n<\/li>\n E (Edges or Links)<\/strong>: The set of connections between nodes.<\/p>\n<\/li>\n<\/ul>\n Definition<\/strong>: Parallel edges (also called multiple edges<\/strong>) occur when two or more edges connect the same pair of vertices<\/strong>. Allowed in:<\/strong> Multigraphs and Pseudographs<\/strong> Definition<\/strong>: A self-loop<\/strong> is an edge that connects a vertex to itself. (A has a self-loop)<\/p>\n Allowed in:<\/strong> Pseudographs<\/strong> Definition<\/strong>: A simple graph<\/strong> is a graph that does not have<\/strong>: Example<\/strong>: A friendship network<\/strong>, where each edge represents a unique connection between two people.<\/p>\n Characteristics<\/strong>:<\/p>\n Each edge connects two distinct vertices<\/strong>.<\/p>\n<\/li>\n At most one edge<\/strong> between any two vertices.<\/p>\n<\/li>\n<\/ul>\n Definition<\/strong>: A multigraph<\/strong> is a graph that allows parallel edges<\/strong> but does not allow self-loops<\/strong>. Allowed<\/strong>: Parallel edges Definition<\/strong>: A pseudograph<\/strong> is a generalized graph<\/strong> that allows both parallel edges and self-loops<\/strong>. Allowed<\/strong>: Parallel edges Simple Graphs<\/strong> \u2192 Social networks, communication systems<\/strong> Parallel Edges<\/strong>: Multiple connections between two nodes.<\/p>\n<\/li>\n Self-Loop<\/strong>: A node connected to itself.<\/p>\n<\/li>\n Simple Graph<\/strong>: No self-loops, no parallel edges.<\/p>\n<\/li>\n Multigraph<\/strong>: Allows parallel edges, but no self-loops.<\/p>\n<\/li>\n Pseudograph<\/strong>: Allows both parallel edges and self-loops.<\/p>\n<\/li>\n<\/ul>\n Would you like practice questions<\/strong> or Python code<\/strong> to implement graphs?<\/p>\n1. Basic Terminology in Graph Theory<\/strong><\/h3>\n
\n
2. Parallel Edges (Multiple Edges)<\/strong><\/h3>\n
Example<\/strong>: In a railway network, two different train routes may connect the same two cities.<\/p>\nGraph Representation<\/strong>:<\/h4>\n
(A) --- (B)<\/span>
\n(A) === (B) <-- Parallel edges<\/span>
\n<\/code><\/div>\n<\/div>\n
Not allowed in:<\/strong> Simple Graphs<\/strong><\/p>\n3. Self-Loop<\/strong><\/h3>\n
Example<\/strong>: In a social network<\/strong>, a person liking their own post<\/strong> can be represented as a self-loop.<\/p>\nGraph Representation<\/strong>:<\/h4>\n
(A) ---- (B)<\/span>
\n| |
\n(A) (C)
\n<\/code><\/div>\n<\/div>\n
Not allowed in:<\/strong> Simple Graphs and Multigraphs<\/strong><\/p>\n4. Simple Graph<\/strong><\/h3>\n
\u00a0Parallel edges
\u00a0Self-loops<\/p>\nGraph Representation<\/strong>:<\/h4>\n
(A) ---- (B)<\/span>
\n| |
\n(C) ---- (D)<\/span>
\n<\/code><\/div>\n<\/div>\n\n
5. Multigraph<\/strong><\/h3>\n
Example<\/strong>: A road network<\/strong> where two different roads exist between the same two cities.<\/p>\nGraph Representation<\/strong>:<\/h4>\n
(A) === (B)<\/span>
\n(A) ---- (C)
\n<\/code><\/div>\n<\/div>\n
Not allowed<\/strong>: Self-loops<\/p>\n6. Pseudograph<\/strong><\/h3>\n
Example<\/strong>: A computer network<\/strong> where a server may have multiple direct connections to the same device, and it may also loop back to itself for redundancy.<\/p>\nGraph Representation<\/strong>:<\/h4>\n
(A) === (B)<\/span>
\n| |
\n(A) ---- (C)
\n<\/code><\/div>\n<\/div>\n
Allowed<\/strong>: Self-loops<\/p>\n7. Comparison Table<\/strong><\/h3>\n
\n\n
\n \nGraph Type<\/th>\n Self-Loops<\/th>\n Parallel Edges<\/th>\n Example<\/th>\n<\/tr>\n<\/thead>\n \n Simple Graph<\/strong><\/td>\n \u00a0No<\/td>\n \u00a0No<\/td>\n Social Network<\/td>\n<\/tr>\n \n Multigraph<\/strong><\/td>\n \u00a0No<\/td>\n \u00a0Yes<\/td>\n Road Network<\/td>\n<\/tr>\n \n Pseudograph<\/strong><\/td>\n \u00a0Yes<\/td>\n \u00a0Yes<\/td>\n Computer Network<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n 8. Applications in Computer Science<\/strong><\/h3>\n
Multigraphs<\/strong> \u2192 Transport networks (railway, road, airline routes)<\/strong>
Pseudographs<\/strong> \u2192 Computer networks, self-feedback loops in circuits<\/strong><\/p>\nConclusion<\/strong><\/h3>\n
\n
Day 07Part 02- Discrete- Parallel edge and Self loop , Simple graph , Multi graph , Pseudo graph.<\/a><\/h3>\n