Blood Relations – Advanced Study Notes
Reasoning Ability – Andaman & Nicobar Islands TET
Level: MIT‑style, “first principles” to “edge‑case” treatment
Audience: Graduate students in Mathematics, Computer Science, or Logic
1. What is a “Blood Relation”?
| Term | Formal Definition | Example |
|---|---|---|
| Blood Relation | A binary relation (R) on a set (S) of living individuals such that (xRy) iff (x) and (y) share a common ancestor (i.e., there exists a chain of parent–child links connecting them). | (\text{John} R \text{Mary}) because they share a grandparent. |
| Kinship | The general social or familial relationship, not limited to blood. | Step‑brother, in‑law, etc. |
| Collaterals | Blood relatives who are not in a direct ancestor–descendant line (siblings, cousins). | Two first cousins. |
| Direct Ancestors / Descendants | One is an ancestor/descendant of the other. | Father–son. |
Remark:
In reasoning tests, “blood relation” usually excludes adoptive or step relationships unless explicitly stated.
2. Formal Properties of the Blood‑Relation Graph
2.1 Graph Representation
Let
- (S) = set of individuals.
- (P \subseteq S \times S) = parent–child relation (directed, not symmetric).
- (R) = blood relation (undirected, reflexive, symmetric, transitive).
Construction:
- Create a directed graph (G_P = (S,,P)).
- Transitive closure of (P) gives all ancestor–descendant pairs.
- Undirected closure (by adding edges for both directions) yields (R).
Thus (R) is the equivalence closure of the parent–child relation.
2.2 Equivalence Relation
Theorem 1.
(R) is an equivalence relation on (S).
Proof.
- Reflexive: Every person shares themselves as a common ancestor (trivially).
- Symmetric: If (x) shares a common ancestor with (y), then (y) shares that ancestor with (x).
- Transitive: If (x) and (y) share ancestor (a), and (y) and (z) share ancestor (b), then (x) and (z) share a common ancestor (either (a) or (b) or an ancestor of both).
∎
Therefore, blood relation partitions (S) into equivalence classes—each class is a blood‑line or family cluster.
2.3 Degree of Blood Relation
Define the degree (d(x, y)) as the length of the shortest path in the undirected graph (G_R) between (x) and (y).
- Immediate relatives (parent, child, sibling) have (d=1).
- First cousins have (d=4) (child → parent → grandparent → parent → child).
Notation
(x \stackrel{d}{\sim} y) ⇔ (d(x, y)=d).
2.4 Collateral vs. Direct Relations
- Direct (Ancestral) Relation: (xRy) and one is an ancestor of the other.
- Collateral Relation: (xRy) but neither is an ancestor of the other.
These can be distinguished algorithmically:
if ancestor(x, y) or ancestor(y, x) then direct
else if connected(x, y) then collateral
else not related
3. Advanced Topics
3.1 Graph‑Theoretic Algorithms for Blood‑Relation Queries
| Problem | Algorithm | Complexity |
|---|---|---|
| Find all members in the same blood‑line as (x) | Depth‑First Search (DFS) or Breadth‑First Search (BFS) on (G_R) | (O( |
| Compute degree (d(x, y)) | BFS from (x) until (y) found | (O( |
| Determine if two people are related | Check connectivity in (G_R) | (O( |
Optimization:
Pre‑compute connected components (Union‑Find / Disjoint Set Union