ThatQuiz Test Library Take this test now
Graph theory - Exam
Contributed by: Leigh
  • 1. Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures used to model relationships between objects. A graph consists of a set of vertices, or nodes, which are connected by edges, or links. Graph theory has applications in various fields such as computer science, social network analysis, and operational research. It helps in solving problems related to connectivity, routing, optimization, and more. Overall, graph theory provides a powerful framework for analyzing and understanding complex systems and relationships.

    What is a graph in graph theory?
A) A mathematical structure consisting of vertices and edges
B) A chart or diagram
C) A pie chart
D) A line graph
  • 2. What is a vertex in a graph?
A) A path between two vertices
B) A line connecting two points in a graph
C) A function in graph theory
D) A point or node in a graph
  • 3. What is an edge in a graph?
A) A connection between two vertices
B) A vertex with no connections
C) A node's color in a graph
D) A loop on a vertex
  • 4. What is a path in graph theory?
A) A cycle in a graph
B) An isolated vertex
C) A disconnected graph
D) A sequence of edges that connect a sequence of vertices
  • 5. In a simple graph, can an edge connect a vertex to itself?
A) No
B) Yes
C) Sometimes
D) Depends on the number of vertices
  • 6. What is the degree of a vertex in a graph?
A) The number of vertices in the graph
B) The distance from one vertex to another
C) The size of the graph
D) The number of edges incident to the vertex
  • 7. What is a planar graph?
A) A disconnected graph
B) A graph with cycles
C) A multigraph
D) A graph that can be drawn on a plane without any edge intersections
  • 8. What is a weighted graph?
A) A graph with only one vertex
B) A graph with maximum number of edges
C) An undirected graph
D) A graph in which a number (weight) is assigned to each edge
  • 9. What is an isomorphism between two graphs?
A) Two disconnected graphs
B) The same number of vertices in both graphs
C) A bijection between their vertex sets that preserves edges
D) A loop on a vertex in both graphs
  • 10. What was the title of Leonhard Euler's paper that is considered the first in graph theory?
A) On the Nature of Graphs
B) Graph Theory and its Applications
C) The Seven Bridges of Königsberg
D) Solutio Problematis ad Geometriam Situs Pertinentis
  • 11. What type of graph allows edges to connect a vertex to itself?
A) Multigraph
B) Undirected graph
C) Directed graph
D) Simple graph
  • 12. Who introduced the term 'graph' in the context of mathematics?
A) Leonhard Euler
B) James Joseph Sylvester
C) Dénes Kőnig
D) Arthur Cayley
  • 13. Which problem in graph theory involves coloring regions of a map with four colors such that no two adjacent regions share the same color?
A) Knight's tour problem
B) Graph connectivity problem
C) Seven Bridges problem
D) Four-color problem
  • 14. Who first posed the four-color problem?
A) Francis Guthrie
B) Augustus De Morgan
C) William Rowan Hamilton
D) Peter Tait
  • 15. Who donated all royalties from their textbook on graph theory to fund the Pólya Prize?
A) Heinrich Heesch
B) Arthur Cayley
C) Dénes Kőnig
D) Frank Harary
  • 16. Which mathematician's work on trees linked graph theory with theoretical chemistry?
A) Arthur Cayley
B) Frank Harary
C) Leonhard Euler
D) Dénes Kőnig
  • 17. Who published Kirchhoff's circuit laws in 1845?
A) Dénes Kőnig
B) Gustav Kirchhoff
C) Leonhard Euler
D) Arthur Cayley
  • 18. What is the name of the method published by Heinrich Heesch in 1969 for solving the four-color problem?
A) Discharging method
B) Coloring algorithm
C) Graph reduction
D) Configuration checking
  • 19. Who wrote the first textbook on graph theory, published in 1936?
A) Arthur Cayley
B) Leonhard Euler
C) Frank Harary
D) Dénes Kőnig
  • 20. What is the name of the problem that involves coloring graphs embedded on surfaces with arbitrary genus?
A) Graph factorization problem
B) Generalized four-color problem
C) Knight's tour problem
D) Graph connectivity problem
  • 21. Who generalized the results of Pólya between 1935 and 1937?
A) Arthur Cayley
B) Heinrich Heesch
C) Frank Harary
D) Nicolaas Govert de Bruijn
  • 22. Who asked for a factory plan minimizing crossings between tracks?
A) Paul Erdős.
B) Karl Menger.
C) Hungarian mathematician Pál Turán.
D) László Lovász.
  • 23. Which branch of algebra focuses on adjacency matrix and its spectrum in spectral graph theory?
A) Group theory
B) Combinatorics
C) Number theory
D) Linear algebra
  • 24. Which theorem states that every finite group is the group of symmetries of a finite undirected graph?
A) Frucht's theorem
B) Paley's theorem
C) Euler's theorem
D) Sylow's theorem
  • 25. Which matrix is a diagonal matrix representing the degree of a vertex?
A) Incidence matrix
B) Laplacian matrix
C) Adjacency matrix
D) Degree matrix
  • 26. Who is credited with the foundational theorem in extremal graph theory?
A) Erdős
B) Szemerédi
C) Mantel
D) Rényi
  • 27. What is an Erdős–Rényi model?
A) An algorithm for graph coloring.
B) A model for generating random graphs.
C) A method for finding spanning trees.
D) A technique for partitioning graphs.
  • 28. In which field are graphs used to model networks of communication and data organization?
A) Computer science
B) Linguistics
C) Biology
D) Physics
  • 29. What is the term for a graph where attributes are associated with vertices and edges, often used to model real-world systems?
A) Causal structure
B) Graph database
C) Network
D) Semantic network
  • 30. What is the principle that gives tree-based structures in linguistics their expressive power?
A) Finite-state transducers
B) Compositionality
C) Feature structures
D) Optimality theory
  • 31. In computational linguistics, what type of network is important for modeling word meaning in terms of related words?
A) Semantic networks
B) Syntactic trees
C) Lattice graphs
D) Graph databases
  • 32. Which organization reflects the usefulness of graph theory to linguistics?
A) VerbNet
B) WordNet
C) Finite-state transducers
D) TextGraphs
  • 33. What is a common method in phonology that uses lattice graphs?
A) Head-driven phrase structure grammar
B) Graph databases
C) Semantic networks
D) Optimality theory
  • 34. Which type of graph is used in finite-state morphology?
A) Finite-state transducers
B) Directed graphs
C) Tree-based structures
D) Lattice graphs
  • 35. In chemistry, what do vertices represent in a molecular graph?
A) Chemical reactions
B) Atoms
C) Bonds
D) Molecules
  • 36. What is represented by edges in the context of chemical graph theory?
A) Molecules
B) Atoms
C) Bonds
D) Chemical reactions
  • 37. What do vertices represent in graphs modeling porous media?
A) Fluids
B) Solids
C) Pores
D) Channels
  • 38. In the context of porous media, what do edges represent?
A) Smaller channels connecting the pores
B) Solid structures
C) Pores themselves
D) Fluid flow paths
  • 39. What can graph structures represent in evolutionary biology?
A) Evolutionary trees
B) Genetic mutations
C) Habitat destruction
D) Species extinction events
  • 40. What is the crossing number for a planar graph?
A) Zero.
B) Equal to the number of vertices.
C) Dependent on the weights assigned to edges.
D) One.
  • 41. Who was influential in the field of graph drawing using linear algebraic methods?
A) Floyd.
B) Euler.
C) W. T. Tutte.
D) Dijkstra.
  • 42. Which data structure is often preferred for sparse graphs due to smaller memory requirements?
A) Incidence matrix
B) Adjacency matrix
C) List structures
D) Matrix structures
  • 43. Which data structure lists the neighbors of each vertex separately?
A) Adjacency matrix
B) Adjacency list
C) Incidence matrix
D) Edge list
  • 44. What is the decomposition of a graph into as few forests as possible called?
A) Cycle double cover
B) Edge coloring
C) Arboricity
D) Graph factorization
  • 45. Which decomposition involves covering each edge exactly twice with cycles?
A) Cycle double cover
B) Edge coloring
C) Arboricity
D) Graph factorization
  • 46. Which problem involves finding a tree connecting a given set of vertices with minimum total edge weight?
A) Minimum spanning tree
B) Steiner tree
C) Hamiltonian path problem
D) Traveling salesman problem
  • 47. Which problem involves finding a spanning tree with the minimum total edge weight?
A) Steiner tree
B) Traveling salesman problem
C) Hamiltonian path problem
D) Minimum spanning tree
Created with That Quiz — the site for test creation and grading in math and other subjects.