Looking for a Tutor Near You?

Post Learning Requirement »
x

Choose Country Code

x

Direction

x

Ask a Question

x

Hire a Tutor
Dubai

Presentation Intersection Graphs

Loading...

Published in: Mathematics
88 Views

Intersection Graphs and it\'s various types

Sumayya H / Dubai

2 years of teaching experience

Qualification: B.Ed (pursuing : 2020 - 2022), MSc Mathematics

Teaches: Maths, Mathematics

Contact this Tutor
  1. INTERSECTION GRAPHS
  2. In Mathematics, Graph theory is the study of graphs, which are mathematical structures used to model pairwise relation between objects. The 'Seven Bridges of Konigsberg' is a historically notable problem in mathematics. Its negative resolution by Leonard Euler in 1936.
  3. Intersection Graphs are very important in both theoretical as well as application point of view. An intersection graph is a graph that represents the pattern of intersections of a family of sets. Erdos Goodman and Posa (1966) credits the observation that all graphs are Intersection graphs. Depending upon the geometric representation, different types of Intersection graphs are defined. Interval, Circular-arc, Permutation, Trapezoid, Chordal, Disk, Circle graphs etc. are some of them
  4. INTERSECTION GRAPHS A graph G=(V,E) is called an intersection graph for a finite family of a non-empty set if there is a one-to-one correspondence between wand V such that two sets in f have non-empty intersection iff their corresponding vertices in V are adjacent. Let ,S2,...Sn} be any family of sets. The intersection graph of Y, denoted by Q($) is the graph having was vertex set with Si adjacent to Sj iff and A graph G is an Intersection graph if there exists a family such that G is isomorphic to
  5. EXAMPLE Let S+ sp Se so be the sets of positive numbers, negative numbers, primes, Fibonacci numbers, even integers and odd integers respectively. Sp Se so
  6. Depending on the nature or geometric configuration of the sets Sl,S2 , different types of intersection graphs are generated. The most useful intersection graphs are : • Interval graphs (S is the set intervals on a real line) • Circular-arc graphs (S is the set of arcs on a circle) Permutation graphs (S is the set of line segments between two line segments) • Chordal graphs (S is the set of connected subgraphs of a tree) • Disk graphs (S is the set of circles on a plane) • Line graphs (S is the set of edges of a graph)
  7. SET-LABELLED INTERSECTION GRAPH Suppose where Sl={xl}, S2={x1 ,x2,x3}, and ,x3,x4,x5}.Then G is isomorphic to Q (5) is as shown below. VI xl xlx3x4x5 xl x2x3 The are the intersection graphs G, both "plain" and "Set-labelled".
  8. FIRST THEOREM OF INTERSECTION GRAPHS Every graph is an Intersection graph INTERSECTION CLASSES Let g be a set of graphs and be a set of sets. Then q is isomorphic to Q (E) if each graph Geo is isomorphic to an intersection graph for some family of sets from y. A set g of graphs is defined to be an 'intersection class' if there is a such that g is isomorphic to Q (Y). INDUCED SUBGRAPHS A set g of graphs is closed under induced subgraphs if G' eg whenever G' is an induced subgraph of some Geo.
  9. VERTEX EXPANSION A set g of graphs is said to be closed under vertex expansion if G' eg whenever G' results from Geg_be repeatedly replacing an existing vertex v by a pair v' ,v" of new adjacent vertices, each having the same pre-existing neighbours as v did. COMPOSITION SERIES A set g of graphs has a composition series if there exists a countable sequence {Gl ,G2,...} of graphs in g such that each Gi is an induced subgraph of some Gi+l and each Geo is the induced subgraph of some Gi. A set g of graphs is an intersection class if i. g is closed under induced subgraphs. ii. (J is closed under vertex expansion. iii. g has a composition series.
  10. INTERSECTION NUMBER Intersection number i(G) is defined to be the minimum cardinality of a set S such that G is an intersection graph of a family of subsets of S. K2: VI
  11. CHORDAL GRAPHS A Chordal graph is one in which all cycles of four or more vertices have a chord which is not an edge that is not a part of the cycle but connects to vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices.
  12. SUBTREE GRAPH A graph G is said to be a subtree graph if it is the intersection graph of a family of subtrees of a tree. The subtree graphs are precisely the chordal graphs. The tree and family of subtrees are called a tree representation of the subtree graph.
  13. 3 4 6 7 The above graph G is a subtree graph isomorphic to Q(TI ,...,T7) Where each Ti is the subtree of the tree in the middle induced by those vertices that contain i. Now let Then the corresponding tree representation of G is:- 245 24 56 4567 46 15 5
  14. A graph is a subtree graph iff it is a chordal graph. SIMPLICIAL VERTEX A vertex is a simplicial vertex of a graph if its neighbours or adjacency set induces a complete graph. VERTEX SEPERATOR A vertex separator is defined to be a set of vertices SCG whose removal divides the graph into two distinct components. A vertex separator S in G is minimal iff the graph obtained by removing S from G has two connected components and such that each vertex in S is both adjacent to some vertex in G.
  15. WEAKLY CHORDAL GRAPH A graph G=(V,E) is weakly chordal iff every cycle of length greater than four in G and the compliment graph G has a chord. (a) (b)
  16. The graph in (b) is the compliment of the graph in (a) which is both chordal and weakly chordal. In (c) the graph is weakly chordal but not chordal. For the graph in (d), it is neither chordal nor weakly chordal. A graph G=(V,E) is chordal weakly chordal. TRIANGULATED GRAPH A triangulated graph is a graph in which for every cycle of length 1>3, there is an edge joining two non-consecutive vertices. DIRAC'S THEOREM A graph G is triangulated iff every minimal vertex separator of G is a clique.
  17. INTERVAL GRAPHS An undirected graph G=(V,E) is said to be an interval graph if the vertex V can be put into one-to-one correspondence with a set I of intervals on the real line such that two vertices are adjacent in G iff their corresponding intervals have a non-empty intersection. That is there is a bijective mapping The set I is called an interval representation of G and G is referred to as the interval graph of I.
  18. Interval representation of the graph G:
  19. TRANSITIVE ORIENTATION PROPERTY A graph G(V,E) satisfies Transitive orientation property. ie., and where u,v,weE. The complement of an interval graph satisfies the transitive orientation property. HEREDITARY PROPERTY An induced subgraph of an interval graph is an interval graph. TRIANGULATED GRAPH PROPERTY Every simple cycle of length strictly greater than 3 possess a chord. An interval graph satisfies the triangulated graph property.
  20. ASTEROIDAL TRIPLE Three vertices form an asteroidal triple in a graph G if, for each two, there exists a path containing those two but no neighbour of the third. (No two vertices of an asteroidal triple can be adjacent) A graph is an interval graph iff it is chordal and has no asteroidal triple. PROPER INTERVAL GRAPH A proper interval graph is the intersection graph of a family of closed intervals of the real line, none of which is properly contained in another.
  21. APPLICATIONS Intersection graphs arise in the process of modelling in many real life situations, specially involving time dependencies or other restrictions that are linear in nature. An important application of intersection graph is to register allocation. A company or organization can run its advertisements. All the program slots of all television channels are modelled as an interval graph. In archaeology an interval graph is used to place a set of items in their chronological order.

Need a Tutor or Coaching Class?

Post an enquiry and get instant responses from qualified and experienced tutors.

Post Requirement

Related PPTs

Upload PPTs

If you have your own PowerPoint Presentations which you think can benefit others, please upload on MyPrivateTutor. For each approved PPT you will get 100 Credit Points and 100 Activity Score which will increase your profile visibility.

Upload Now
Home > PowerPoint Slides > Presentation Intersection Graphs