Graphs vs Trees Quiz

Definition and Basics of Graphs

• A graph is a non-linear data structure consisting of a finite set of nodes with edges between them.
• A graph G can be formally represented as (V, E), where V is a finite set of nodes, and E is a set of pairs of nodes.

Graph vs. Tree

• A tree is a connected graph with no loops or cycles.
• Graphs can have cycles and disconnected components, while trees are connected with no cycles.
• In a tree, each node (except the root) has exactly one parent, whereas in a graph, nodes can have multiple parents or no parents.

Node and Edge Relationships

• Nodes (or vertices) represent entities such as people, cities, computers, words, etc.
• Edges (x, y) represent relationships between entities x and y, such as distance, friendship, child-parent relationships, etc.

Graph Terminology

• A vertex (or node) is an individual data element of a graph.
• An edge is a connecting link between two vertices and can be undirected, directed, or weighted.
• Undirected edges are bidirectional, while directed edges are unidirectional.
• Weighted edges have a cost or value associated with them.

Edge Types and Graph Properties

• Parallel edges or multiple edges have the same endpoints.
• A self-loop is an edge that connects a node to itself.
• A simple graph has no parallel or self-loop edges.
• Adjacent nodes are connected by an edge.
• A path is a sequence of vertices that connect two nodes in a graph.

Graph Connectivity

• An undirected graph is connected if there is a path between every pair of nodes.
• A disconnected graph is one where there is no path between some pair of nodes.

Indegree and Graph Types

• The indegree of a node is the number of edges incident to it.
• Types of graphs include undirected, directed, complete, and weighted graphs.