Intro to Graphs Flashcards
What is a graph in mathematics?
A graph is a collection of vertices (nodes) and edges (connections) between them.
What are the different types of graphs? (not on test)
Undirected Graph: Edges have no direction.
Directed Graph (Digraph): Edges have a direction.
Weighted Graph: Edges have weights or costs.
Unweighted Graph: Edges have no associated weight.
Complete Graph: Every pair of vertices is connected.
Bipartite Graph: Vertices are divided into two disjoint sets.
Tree: A connected, acyclic graph.
What are the common ways to represent a graph in a computer?
Adjacency List: Stores nodes and their neighbors.
Adjacency Matrix: A 2D matrix where an entry (i, j) is 1 if there’s an edge between node i and j.
Incidence Matrix: Represents edges and their incidence on nodes.
What is the Graph Neural Network (GNN) approach?
A deep learning model designed to process graph-structured data by message passing between nodes.
What are some types of Graph Neural Networks (GNNs)?
GCN (Graph Convolutional Networks): Generalizes convolution to graphs.
GAT (Graph Attention Networks): Uses attention mechanisms for node importance.
GIN (Graph Isomorphism Networks): Focuses on distinguishing different graph structures.
What is Dijkstra’s Algorithm used for?
Finding the shortest path from a source vertex to all other vertices in a weighted graph.
What is an Eulerian Path?
A path that visits every edge of a graph exactly once.
What is a Hamiltonian Path?
A path that visits every vertex of a graph exactly once.
What is the Minimum Spanning Tree (MST)?
A subset of edges that connects all vertices with minimum total edge weight and no cycles.
What is Betweenness
A measure of how often a node or edge appears on shortest paths between other nodes.
What is the Girvan–Newman Algorithm?
A community detection algorithm that removes edges with high betweenness to split graphs into communities.
What are the steps of the Girvan–Newman Algorithm?
Compute Edge Betweenness for all edges.
Remove the edge with the highest betweenness.
Recompute betweenness and repeat until the graph splits into communities.
What are Graph Databases?
Databases designed to store and query graph data efficiently (e.g., Neo4j, Amazon Neptune).
