Graphs MCQ

Test your knowledge with important Graphs MCQ and their applications. These MCQs are beneficial for competitive exams too. Explore 30 + more Graphs MCQs at Bissoy

• A free semilattice has the _______ property.
  ক

  intersection

  খ

  commutative and associative

  গ

  identity

  ঘ

  universal
• Every poset that is a complete semilattice must always be a _______
  ক

  sublattice

  খ

  complete lattice

  গ

  free lattice

  ঘ

  partial lattice
• The graph is the smallest non-modular lattice N5. A lattice is _______ if and only if it does not have a _______ isomorphic to N5.
  ক

  non-modular, complete lattice

  খ

  moduler, semilattice

  গ

  non-modular, sublattice

  ঘ

  modular, sublattice
• A sublattice(say, S) of a lattice(say, L) is a convex sublattice of L if _________
  ক

  x>=z, where x in S implies z in S, for every element x, y in L

  খ

  x=y and y<=z, where x, y in S implies z in S, for every element x, y, z in L

  গ

  x<=y<=z, where x, y in S implies z in S, for every element x, y, z in L

  ঘ

  x=y and y>=z, where x, y in S implies z in S, for every element x, y, z in L
• The graph given below is an example of _________
  ক

  non-lattice poset

  খ

  semilattice

  গ

  partial lattice

  ঘ

  bounded lattice
• A ________ has a greatest element and a least element which satisfy 0<=a<=1 for every a in the lattice(say, L).
  ক

  semilattice

  খ

  join semilattice

  গ

  meet semilattice

  ঘ

  bounded lattice
• ______ and _______ are the two binary operations defined for lattices.
  ক

  Join, meet

  খ

  Addition, subtraction

  গ

  Union, intersection

  ঘ

  Multiplication, modulo division
• If every two elements of a poset are comparable then the poset is called ________
  ক

  sub ordered poset

  খ

  totally ordered poset

  গ

  sub lattice

  ঘ

  semigroup
• In the poset (Z+, |) (where Z+ is the set of all positive integers and | is the divides relation) are the integers 9 and 351 comparable?
  ক

  comparable

  খ

  not comparable

  গ

  comparable but not determined

  ঘ

  determined but not comparable
• A Poset in which every pair of elements has both a least upper bound and a greatest lower bound is termed as _______
  ক

  sublattice

  খ

  lattice

  গ

  trail

  ঘ

  walk
• Suppose P1 is a partially ordered class and a cut of P1 is pair (D, T) of nonempty subclasses of P1 satisfies which of the following properties?
  ক

  D∩T=Ø

  খ

  D∪T=P1

  গ

  xyz∈T

  ঘ

  z∈T and zx∈D
• In a poset (S, ⪯), if there is no element n∈S with m<n, then which of the following is true?
  ক

  an element n exists for which m=n

  খ

  An element m is maximal in the poset

  গ

  A set with the same subset of the poset

  ঘ

  An element m is minimal in the poset
• In which of the following relations every pair of elements is comparable?
  ক

  ≤

  খ

  !=

  গ

  >=

  ঘ

  ==
• The relation ≤ is a partial order if it is ___________
  ক

  reflexive, antisymmetric and transitive

  খ

  reflexive, symmetric

  গ

  asymmetric, transitive

  ঘ

  irreflexive and transitive
• Which of the following relation is a partial order as well as an equivalence relation?
  ক

  equal to(=)

  খ

  less than(<)

  গ

  greater than(>)

  ঘ

  not equal to(!=)
• If the partial order of a set has at most one minimal element, then to test whether it has a non-crossing Hasse diagram its time complexity __________
  ক

  NP-complete

  খ

  O(n2)

  গ

  O(n+2)

  ঘ

  O(n3)
• If a partial order is drawn as a Hasse diagram in which no two edges cross, its covering graph is called ______
  ক

  upward planar

  খ

  downward planar

  গ

  lattice

  ঘ

  biconnected components
• Hasse diagrams are first made by ______
  ক

  A.R. Hasse

  খ

  Helmut Hasse

  গ

  Dennis Hasse

  ঘ

  T.P. Hasse
• G is an undirected graph with n vertices and 26 edges such that each vertex of G has a degree at least 4. Then the maximum possible value of n is ___________
  ক

  7

  খ

  43

  গ

  13

  ঘ

  10
• An undirected graph has 8 vertices labelled 1, 2, …,8 and 31 edges. Vertices 1, 3, 5, 7 have degree 8 and vertices 2, 4, 6, 8 have degree 7. What is the degree of vertex 8?
  ক

  15

  খ

  8

  গ

  5

  ঘ

  23
• In a finite graph the number of vertices of odd degree is always ______
  ক

  even

  খ

  odd

  গ

  even or odd

  ঘ

  infinite
• Degree of a graph with 12 vertices is _______
  ক

  25

  খ

  56

  গ

  24

  ঘ

  212
• A simple graph can have _______
  ক

  multiple edges

  খ

  self loops

  গ

  parallel edges

  ঘ

  no multiple edges, self-loops and parallel edges
• Disconnected components can be created in case of ___________
  ক

  undirected graphs

  খ

  partial subgraphs

  গ

  disconnected graphs

  ঘ

  complete graphs
• What is a complete digraph?
  ক

  connection of nodes without containing any cycle

  খ

  connecting nodes to make at least three complete cycles

  গ

  start node and end node in a graph are same having a cycle

  ঘ

  connection of every node with every other node including itself in a digraph
• Let, D = <A, R> be a directed graph or digraph,then D’ = <A’, R’> is a subgraph if ___________
  ক

  A’ ⊂ A and R’ = R ∩ (A’ x A’)

  খ

  A’ ⊂ A and R ⊂ R’ ∩ (A’ x A’)

  গ

  R’ = R ∩ (A’ x A’)

  ঘ

  A’ ⊆ A and R ⊆ R’ ∩ (A’ x A’)
• A directed graph or digraph can have directed cycle in which ______
  ক

  starting node and ending node are different

  খ

  starting node and ending node are same

  গ

  minimum four vertices can be there

  ঘ

  ending node does not exist