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