3.2
>> graph is noting but a set of vertices and edges represented by G(V, E)
>> Directed graphs:- edges are directed by arrows
>> Undirected graphs :- edges are not directed by arrows.
>>weighted graphs :- edges have some number
>>dregree of vertex :- number of edges incident on vertex (self loop is count as 2)
>> Path :- if length of path = n then n edges and n+1 vertices in path.
> simple path :- no repeated vertices,no multi edges(parallel edges) between 2 vertices.
> elementary path :- no vertices appear more than once.
> Circuit or Closed Path: path which starts and ends at the same vertex, i.e., v0=vn.
> Simple Circuit Path: The simple circuit is a simple path which is a circuit.
>>Pendant Vertex: vertex with degree 1
Pendant Edge: edge incident on vertex with degreee 1
Odd Vertex: vertexes having odd degree
Even Vertex: vertexes having even degree
Incident Edge: if edge e connects a and b then e is incident to a and b
Adjacent Vertices: if b is connected to a, c and d through edges then b is adjacent to a, c and d.
>>Isolated Vertex: A vertex with degree 0 is called Isolated Vertex.
>> Handshaking theorem :- The sum of degrees of the vertices of a graph is twice the number of edges.
Σ degG (V) = 2E
>>Corollary: In a graph, the total number of odd degree vertices is even.
>>Types of graphs :
>Null ;-have all isolated vertices.
>Multigraph :- graph having multiple edges between 2 vertices.
>Undirected complete graph :- every vertex is connected to every other vertex.
if it have n vertex then it will have 
edges and is denoted by Kn
.
> Regular graph :- all the vertices have same degree. if their are n vertices and every vertex have n-1 degree then it is called completer regular graph.
>Bipartite Graph: vertices 2 parts m divide ho skti hon. this is denoted by Kmn
where m and n are number of vertices in each part.
>>Representation
2.Incidence Matrix Representation:
>Directed Graphs :-
1.Adjacency Matrix Representation:
2.Incidence Matrix Representation:
>> Isomorphic graphs :-
Consider a graph G(V, E) and G* (V*,E*) are said to be isomorphic if there exists one to one correspondence i.e.
f:V→V* such that {u, v} is an edge of G if and only if {f(u), f(v)} is an edge of G*.
Every isomorphic graph must have adjicency matrix representation
>>Homeomorphic Graphs:
Two graphs G and G* are said to homeomorphic if they can be obtained from the same graph
a and b obtained from c.
>>Note: An isomorphism of G to G is called an automorphism.
>>Sub graph:
A subgraph of a graph G=(V, E) is a graph G'=(V',E') in which V'⊆V and E'⊆E and each edge of G' have the same end
vertices in G' as in graph G.
>> Spanning Subgraph:
A graph G1 is called a spanning subgraph of G if G1 contains all the vertices of G.
shortest path in weighted graphs :-
Path Length: The length of path is sum of weights of the edges on that path.
Source: The starting vertex of the graph from which we have to start to find the shortest path.
Destination: The terminal or last vertex up to which we have to find the path.
>>
Dijkstra's algorithm:
it works on both directed and undirected graphs represented by cost adjacency matrix and cost is the weight of edge which is always postive in this algorithm if cost is -ve then this algo may give wrong results.
Solution:
Step 1: Include the vertex K is S and determine all the direct paths from K to all other vertices without going
through any other vertex.
Since, n-1 vertices included in S. Hence we have found the shortest distance from K to all other vertices. Thus, the
shortest distance between K and L is 8 and the shortest path is K, c, b, L.
Euler path and circuits :-
(i) List the degree of all vertices in the graph.
(ii) If any value is zero, the graph is not connected and hence it cannot have Euler path or Euler circuit.
(iii) If all the degrees are even, then G has both Euler path and Euler circuit.
(iv) If exactly two vertices are odd degree, then G has Euler path but no Euler circuit.
Halmiltonian paths and circuits :-
A simple path in a graph that passes through every vertex exactly once is called a
Hamiltonian path.A simple circuit in a graph that passes through every vertex exactly once is called a
Hamiltonian circuit.
>>Note: Euler’s circuit contains each edge of the graph exactly once. In a Hamiltonian cycle, some edges of the graph
can be skipped.
planer graphs and euler formula.
Planar Graph: A graph is said to be planar if it can be drawn in a plane so that no two edges cross each other at a
non-vertex point..
Finite Region:
Infinite Region:
Properties of Planar Graphs:
>>If a connected planar graph G has e edges and r regions, then r ≤
e.
>>If a connected planar graph G has e edges, v vertices, and r regions, then v-e+r=2.
>>If a connected planar graph G has e edges and v vertices, then 3v-e≥6.
>>A complete graph(every vertex connected to each other.) Kn is a planar if and only if n<5.
>>A complete bipartite graph Kmn is planar if and only if m<3 or n>3.
Properties of Non-Planar Graphs:
A graph is non-planar if and only if it contains a subgraph homeomorphic to K5 or K3,3
>> v-e+r=2 this is eulers formula and it deals with the shape called polyhedron(all flat faces no curved face)
>>Note –“If G is a connected planar graph with e edges and v vertices, where v≥3, then e≤3v-6 Also G cannot have a
vertex of degree exceeding 5.”
Comments
Post a Comment