GTC
Unit-1Introduction to Graph Theory
Q1) Explain different Types of Graphs.A1)Acyclic directed graphA finite directed graph that has no driven cycles is an acyclic directed graph.Directed graphA directed graph is a graph where the edges have direction; that is, pairs of vertices are ordered.
MultigraphThe graph that occurs when you delete several edges is a condensation of a multigraph, leaving just one edge at any two points.A multigraph is a loop-less graph, but which may have several edges.
A graph with no edges is a null graph. Maybe it has one or two vertices.
An oriented graph is a led graph with no symmetrical pairs of directed edges.The graph is called a related graph if a graph has a path between each pair of vertices (there is no vertex not connected to an edge).If, through repeated edge contractions or deletions, a graph G 'can be constructed from a graph G, the graph G' is a graph minor of G. Inverted GraphA graph with the same vertices but none of the same edges is an inverted graph G 'of G; two vertices in G' are adjacent if and only if in G they were not adjacent. Plain graphA plain graph is a graph with no loops or many edges at all. No multiple edges implies that the same endpoints are not visible on two edges. SubgraphA subgraph is a graph whose vertices and edges are part of another graph's vertices and edges (the supergraph). Symmetric graphA symmetric graph is a D-directed graph where the inverted arc (y,x) is also in D for each arc (x,y). Trivial GraphA graph with just a single vertex is a trivial graph. Undirected graphAn undirected graph is a graph where no path is given to any of the edges; the pairs of vertices representing each edge are unordered. SubgraphsA Subgraph Q of a graph R is a graph whose vertex set V(Q) is a subset of the vertex set V(R), that is V(Q)⊆V(R), and whose edge set E(Q) is a subset of the edge set E(R), that is E(Q)⊆E(R).
Q (Subgraph of R) R
|
|
|
|
Q2) Explain Complement of graph.A2)Let 'G-' be a simple graph with some vertices like 'G' and in 'G-' there is an edge {U, V}, if the edge is not present in G. This means that two vertices in 'G' are adjacent if the two vertices in G are not adjacent.If in another graph II, the edges existing in graph I are absent, and if both graph I and graph II are combined to form a complete graph, then graph I and graph II are referred to as mutual complements.
Notice − A mixture of two additional graphs produces a complete graph.If 'G' is any simple graph, then|E(G)| + |E('G-')| = |E(Kn)|, where n = number of vertices in the graph.
|
Q3) What is Graph isomorphism?A3) Graph isomorphism is an equivalence relationship on graphs which, as such, splits the class into equivalence groups on all graphs. An isomorphism class of graphs is called a group of graphs isomorphic to one another. The two graphs shown below are isomorphic, despite their different looking drawings.
Two isomorphic plots A and B and one non-isomorphic plot C; Each of them has four vertices with three corners.
|
Q4) Explain Vertex DegreeA4) The degree of a vertex, in graph theory, is the number of edges connecting it. Vertex a has degree 5 in the following example, and the rest has degree 1. A degree 1 vertex is referred to as a "end vertex"
Q5) Define vertex, node, edge contraction, graph transversal and hamltonian cycle.A5)A point or circle is a vertex, also called a node. It is the basic unit from which graphs are generated.By combining the two vertices he used to merge, an edge contraction involves removing an edge from a graph.A graph traversal in computer science and computer-based graph theory is an analysis of a graph in which one by one the vertices are visited or modified.A Hamiltonian cycle is a loop that is closed where each node is visited precisely once. Q6) Define Euler path and Euler circuitsA6) An Euler path is a path that uses any graph edge once precisely.
An Euler circuit is a circuit that uses each graph edge once precisely.
An Euler path begins and finishes at multiple vertices.The circuit of An Euler begins and ends at the same vertex. Q7) Define graph theory.A7) The analysis of lines and points is Graph Theory.It is a mathematics sub-field that deals with graphs: diagrams that contain points and lines and that also represent mathematical truths in a pictorial way. The theory of graphs is the analysis of the interaction of edges and vertices. A graph is formally a pair (V, E), where a finite set of vertices is V and a finite set of edges is E.
|
|
|
|
0 matching results found