Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Edge Elimination and Orientation in Graphs

In course

MGT-416: Causal inference

Students will learn the core concepts and techniques of network analysis with emphasis on causal inference. Theory and application will be balanced, with students working directly with network data throughout the course. ...

Description

This lecture covers the concepts of edge elimination and orientation in graphs, including zero order and first order tests, tree graphs, complete graphs, statistical orientation, and logical orientation. The instructor explains the process of eliminating edges in graphs and determining the orientation of nodes based on different tests.

Instructor

Negar Kiyavash

Official source

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related concepts (20)

Graph isomorphism

In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H such that any two vertices u and v of G are adjacent in G if and only if and are adjacent in H. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection. If an isomorphism exists between two graphs, then the graphs are called isomorphic and denoted as . In the case when the bijection is a mapping of a graph onto itself, i.

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

Line graph

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G). The name line graph comes from a paper by although both and used the construction before this.

List of graphs

This partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.

Chordal graph

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree.

Related lectures (29)

Graphs: Properties and Representations

Covers graph properties, representations, and traversal algorithms using BFS and DFS.

Automorphism groups: Trees and Graphs

Explores automorphism groups in trees and graphs, focusing on ends and types of automorphisms.

Automorphism Groups: Trees and Graphs III

Explores automorphism groups of trees and graphs, including actions on trees and group homomorphisms.

Graphical Models: Representing Probabilistic Distributions

Covers graphical models for probabilistic distributions using graphs, nodes, and edges.

Automorphism groups of trees and graphs II