Lecture 8: Equivalence Relations and Partial Orders

- Equivalence Relations
- Partial Orders



# 等价关系 Equivalence relations

等价关系是一种捕捉“相等”这一概念的二元关系，它必须满足以下三个属性：

- 自反性。每个对象都应当与自身相等。$(x,x) \in R$
- 对称性。如果 $(x,y) \in R$，那么 $(y,x) \in R$
- 传递性。如果$(x,y) \in R, (y,z) \in R$，那么 $(x,z) \in R$

根据定义，一个二元关系 $R$ 是集合 $ S $上的等价关系，当且仅当它满足自反性（R）、对称性（S）和传递性（T）。

## 等价类 Equivalence Classes

假设 $R \subseteq S \times S$ 是一个等价关系。

集合 $S$ 中的元素 $s$ 的等价类（记作 $[s]$）是所有与 $s$ 相等（根据关系 $R$）的元素的集合。形式上，有：

$$
[s] = \{ t \in S | sRt \}
$$

等价类的概念指，如果你取了集合 $S$ 中的任意一个元素 $s$ 并且找到了所有与它相等的元素 $t$，那么这些元素 $t$ 形成的集合就是 $s$ 的等价类。

$s$ 和 $t$ 在关系 $R$ 下相等当且仅当它们属于同一个等价类，即 $[s]=[t]$。

## 划分 Partitions

集合 $S$ 的划分是一组集合 $S_1,S_2,...S_k$，满足：
- 对于任意不相同的 $i,j$，均有 $S_i \cap S_j=\empty$，即任意两集合不相交。
- 集合 $S$ 是这些集合的并集，即 $S=S_1 \cup S_2 \cup ... \cup S_k$。

如果你有集合 $S = S_1 \cup ... \cup S_k$，那么划分实际上也定义了一个等价关系。每个元素都有属于自己的一个子集 $S_i$。如果想定义两个元素等价，我们可以定义等价关系 $\sim \subseteq S \times S$ 上如下：

- $s\sim t$ 当且仅当 $s$ 和 $t$ 属于同一个子集 $S_i$。

该定义表示 $s$ 与 $t$ 等价。


# 偏序集 Partial Order

如果一个关系 $\preceq$ 在集合 $S$ 上是偏序地，需要满足以下三个条件：

- 自反性。
- 反对称性。
- 传递性。

集合 $S$ 与偏序关系 $\preceq$ 一起构成一个偏序集，简称为poset。

以下是一些常见的偏序集例子：

- $(Z, \le)$
- $(N, |)$

## 哈斯图 Hasse diagram

它是一种表示有限偏序集的图形工具。

- 每个节点代表偏序集 $S$ 中的一个元素。
- 如果 $x \prec y$，并且中间没有元素 $z$ 使得 $x \prec z \prec y$，那么在哈斯图中从 $x$ 向上画一条到 $y$ 的边。

![image.png](/static/img/29e57ae7e391b8de6ed128150e61ba6b.image.webp)

## 元素排序 Ordering Concepts

在偏序集 $(S, \preceq)$ 中，一些基本概念如下：

- 极小元素 Minimal element：在偏序集 $(S, \preceq)$ 中，如果不存在另一个不同的元素 $y$ 满足 $y \preceq x$，那么称 $x$ 为极小元素。
- 极大元素 Maximal element：在偏序集 $(S, \preceq)$ 中，如果不存在另一个不同的元素 $y$ 满足 $x \preceq y$，那么称 $x$ 为极大元素。
- 最小元素 Minimum element：如果对于所有 $y \in S$，都有 $x \preceq y$，那么 $x$ 被称为最小元素。
- 最大元素 Maximum element：如果对于所有 $y \in S$，都有 $y \preceq x$，那么 $x$ 被称为最大元素。

:::note{title="注"}
可能会有多个极小元素或极大元素。

如果最大元素/最小元素存在，那么它们就是唯一的极小元素/极大元素。

极小元素/极大元素在有限偏序集中总是存在，但在无限偏序集中不一定存在。
:::

- 上界 upper bound：如果 $x$ 满足对集合 $A$ 中的所有元素 $a$，都有 $a \preceq x$，那么 $x$ 就是 $A$ 的一个上界。
- 下界 lower bound：如果 $x$ 满足对集合 $A$ 中的所有元素 $a$，都有 $x \preceq a$，那么 $x$ 就是 $A$ 的一个下界。
- 上界集合 set of upper bounds：$ub(A)=\{x: a \preceq x \text{ for all } a \in A\}$
- 下界集合 seet of lower bounds：$lb(A)=\{x: x \preceq a \text{ for all } a \in A\}$
- 最小上界 least upper bound：如果存在，集合 $A$ 的最小上界是上界集合中的最小元素，记作 $lub(A)$。也称上确界。
- 最大下界 greatest lower bound：如果存在，集合 $A$ 的最大下界是下界集合中的最大元素，记作 $glb(A)$。也称下确界。

:::note{title="注"}

要证明一个元素 $x$ 是集合 $A$ 的下确界，你需要证明：

1. $x$ 是 $A$ 的一个下界，即对于所有 $a \in A$，都有 $x \preceq a$。
2. $x$ 是所有下界中最大的元素，即对于所有满足条件的 $y$，都有 $y \preceq x$。

:::

- 格 lattice：对于偏序集 $S, \preceq$，如果对于任意两个元素 $x,y \in S$，它们的上确界 $lub(S)$ 和下确界 $glb(S)$ 都存在，那么称该偏序集为一个格。
- 完备格 complete lattice：对于偏序集 $S, \preceq$，如果对于 $S$ 的任意子集 $A$，它的上确界 $lub(A)$ 和下确界 $glb(A)$ 也都存在，那么称该偏序集为一个完备格。

:::note{title="注"}
有限格总是完备格。因为在有限的情况下，你总是可以通过比较有限个元素来找到最小上界和最大下界。

一个无限格不一定有对其任意无限子集的最小上界或最大下界，尤其是可能不存在一个界限能够涵盖所有元素。
:::

## 全序 Total orders

全序是一种特殊的偏序关系，它除了满足偏序的基本条件（自反性、反对称性、传递性）之外，还满足线性性（Linearity）。这意味着集合中的任何两个元素都可以进行比较：

- 对于所有的 $x,y$，要么出现 $x \le y$，要么出现 $y \le x$。（如果 $x = y$ 则两者都成立）

在有限集合上，所有的全序关系都是“同构”的。这意味着在有限集合上的任意两个全序关系，你总能找到一种方式将一个全序集映射到另一个全序集，保持其顺序结构不变。

在无限集合上，存在多种全序关系的可能性。这表示无限集合上的全序可以有多种不同的结构，不能简单地通过同构关系进行映射。


## 拓扑排序 Topological Sort

对于一个偏序集 $(S, \preceq)$，任何与偏序 $\preceq$一致的全序 $\le$ 都成为拓扑排序。这意味着在偏序关系中如果 $a \preceq b$，那么在拓扑排序中一定有 $a \le b$。

![image.png](/static/img/29414eef40e30e744a95c940d0515ab6.image.webp)


## 良序集 Well-Ordered Sets

良序集是一个偏序集，其中每个子集都有一个最小元素。良序集不要求有最大元素。

自然数集N是一个良序集，每个子集都一定有一个最小元素。

$$
N = \{0,1,2,...\}
$$

良序集是一个重要的数学工具，用于证明程序的终止。因为在良序集中，你可以总是找到一个最小的元素，所以在迭代或递归的情况下，你可以保证每个步骤都是向终止条件靠近，而不是无限进行下去。这在证明算法正确性和计算复杂性时非常有用。

## 笛卡尔积乘积序 Orders for Cartesian products

给定两个偏序集 $(S, \preceq_S)$ 和 $(T, \preceq_T)$，可以定义它们的乘积序如下：

对于 $S \times T$ 中的任意两个元素 $(s,t)$ 和 $(s',t')$，当且仅当 $s \preceq_S s'$，并且 $t \preceq_T t'$ 时，有：

$$
(s,t) \preceq (s',t')
$$

乘积序有以下特点：

- 没有隐含的权重。这意味着在比较两个元素时，$S$ 和 $T$ 中的元素被平等对待。
- 没有对任何组成部分的偏见。乘积序中没有一个方向比另一个更重要。
- 通常，乘积序只是一个偏序，即使是将全序结合起来也是如此。也就是说，即使 $S$ 和 $T$ 上各自的序是全序，它们的乘积也不一定是全序。

乘积序是理解多维数据结构中元素顺序的重要概念，例如，在数据库、多维数组或是在编程语言中处理多个有序集合时非常有用。它允许我们从多个维度组合和比较数据点。

## 笛卡尔积字典序 Orders for Cartesian lexicographic

给定两个偏序集 $(S, \preceq_S)$ 和 $(T, \preceq_T)$，可以定义它们的字典序如下：

对于 $S \times T$ 中的任意两个元素 $(s,t)$ 和 $(s',t')$，当 $s \preceq_S s'$，或者 $s=s', t \preceq_T t'$ 时，有：

$$
(s,t) \preceq_{lex} (s',t')
$$

这意味着先比较第一个元素，如果第一个元素相同，再比较第二个元素。

字典序有以下特点：

- 没有隐含的权重：即没有一个组件比另一个更重要。
- 当组合两个全序时，会给出全序。
- 可以扩展到单词：这意味着可以用来对字符串数组进行排序，比如在字典中排序单词一样。
- 不适合枚举。

字典序是一种重要的序，因为它允许我们对组合数据进行有序排列，这在数据结构、数据库索引以及编程语言中处理字符串时特别有用。它在数学和计算机科学中有广泛的应用。

COMP9020 4.2 Equivalence Relations and Partial Orders

Lecture 7: Relations

- Definition and Examples
- Binary Relations
- Properties of Binary Relations
- Functions




# 定义与例子 Definition and Examples

## 关系 Relations

n元关系（n-ary relation）是n个集合的笛卡尔积的子集，记作：

$$
R \subseteq S_1 \times S_2 \times ... \times S_n
$$

特殊地，当 $n=2$ 时，我们称之为二元关系（binary relation），记作：

$$
R \subseteq S \times T
$$

并且展示相关联的数对时，写作：

$$
(x,y) \in R \ \ \ \ \ or \ \ \ \ \ R(x,y) \ \ \ \ \ or \ \ \ \ \ xRy
$$

笛卡尔积的结果集合 $U=S_1 \times S_2 \times ... \times S_n$ ，称之为 $R$ 的定义域（domain）。如果关系 $R$ 定义域在 $U$ 上，我们就说 $R$ 是 $U$ 上的关系。

## 例子


![image.png](/static/img/684ffb6e0838df2fffb75dca1eb69124.image.webp)


![image.png](/static/img/a1403027b35b1d219cf2699836f206f2.image.webp)

在这个关系中，enrolment显然是学生与课程的对（pair），但应当不是笛卡尔积的全集（因为不太可能每一名学生都会修掉所有的课）。


![image.png](/static/img/2c9479f0acdacecec9c23c0494bb42e3.image.webp)


## 定义关系 Defining Relations

有以下几种方式定义一个关系 $R$ ：

1. 通过明确地列举相关的k元组来定义：这里的k元组指的是在二元关系的情况下的有序对。
2. 通过识别大的笛卡尔积内部的相关元组的属性来定义：这意味着关系可以通过满足特定关系的元组的等式/不等式/关系式等描述。
3. 通过其他关系构建定义：例如通过交集，并集，补集等。

![image.png](/static/img/ca0b1e6a93529b517ee1e5f16a833ef5.image.webp)


![image.png](/static/img/a5d990dc197e36184043db2e8ce6f35b.image.webp)

# 二元关系 Binary relations

在集合S和T之间的二元关系是 $S \times T$ 的子集，即有序对的集合。

特殊的二元关系例子：

- 恒等关系（Identity）：这是对角线关系，也称等价琯溪，定义为 $I = \{(x,x)|x \in S\}$，其中每个元素与自身形成对。
- 空关系（Empty）：不包含任何元素的关系，记作 $\empty$。
- 全域关系（Universal）：包含所有可能有序对的关系，定义为 $U=S \times T$。

## 定义二元关系的方法 Definition binary relations

### 基于集合定义 Set-based definitions

参考：定义关系部分。

### 矩阵描绘 Matrix representation


![image.png](/static/img/5f4d3658fb41e596f5aeeeafb039d50d.image.webp)

### 图像描述 Graphical representation

#### 集合图表示

![image.png](/static/img/d86bc96487e7281616b35f4a4c5b2777.image.webp)

#### 有向图表示

![image.png](/static/img/5e1b1a707374c4340e06f26068f1a15a.image.webp)

## 二元关系操作 Operations for binary relations

### 逆关系 Converse

如果有一个关系 $R \subseteq S \times T$，那么它的逆关系 $R^←$ 定义为：

$$
R^←=\{(t,s) \in T \times S: (s,t) \in R\}
$$

这意味着在逆关系中，每个有序对的元素顺序会被反转。并且，显然有：

$$
(R^←)^←=R
$$

### 复合关系 Composition

如果 $R_1 \subseteq S \times T$ 并且 $R_2 \subseteq T \times U$，那么它们的符合关系 $R_1 ; R_2$ 定义为：

$$
R_1 ; R_2 = \{ (s,u) \in S \times U: \exist t \in T \text{ such that } (s,t) \in R_1,(t,u) \in R_2 \}
$$

复合关系意味着从集合S到U存在一个通过集合T中介的关系路径。


## 关系映像 Relational images

> 想象一下你在学校的学生和他们参加的俱乐部之间有一个列表，这个列表就是一个关系，它告诉你哪个学生参加了哪个俱乐部。
> 
> 现在，如果你想知道某个特定学生参加了哪些俱乐部，你就会查找与这个学生相关的所有俱乐部，这就是关系映像。就像你拿着学生的名字去映射找出他们参加的所有俱乐部。
> 
> 反过来，如果你手头有一个俱乐部的名单，你想找出所有参加这个特定俱乐部的学生，你就会查找与这个俱乐部相关的所有学生，这就是关系预映像。这就像是你从俱乐部的角度出发，反向映射回去找到所有相关的学生。
> 
> 简单来说，关系映像就是从一个集合（比如学生）出发，找到与它们相关联的另一个集合（比如俱乐部）中的成员。而关系预映像则是反过来的操作。

给定关系 $R \subseteq S \times T$，$A \subseteq S$，并且 $B \subseteq T$。

### 关系映像 Relational image

关系映像 $R(A)$ 被定义为：

$$
R(A)=\{ t \in T: (s,t) \in R \text{ for some } s \in A \}
$$

简而言之，$R(A)$ 包含了所有与集合A中的元素通过关系R相关联的T中的元素。

### 关系预映像 Relational pre-image

关系预映像 $R^←(B)$ 被定义为：

$$
R^←(B)=\{ s \in S: (s,t) \in R \text{ for some } t \in B \}
$$

简而言之，$R^←(B)$ 包含了所有能够通过关系R找到与B中元素相对应的S中的元素。


# 二元关系的性质 Properties of Binary Relations

- 函数式（Fun） functional：对于每个 $S$ 中的元素 $s$，在关系 $R$ 中至多与一个 $T$ 中的元素 $t$ 关联。也就是说每个 $s$ 都至多映射到一个 $t$。
    ![image.png](/static/img/b07e9f281d66f46a26a9780a0bde173f.image.webp)
- 全域性（Tot） total：对于每个 $S$ 中的元素 $s$，在关系 $R$ 中至少与一个 $T$ 中的元素 $t$ 关联。也就是说每个 $s$ 都至少映射到一个 $t$。
- 单射（Inj） injective：对于每个 $T$ 中的元素 $t$，在关系 $R$ 中至多与一个 $S$ 中的元素 $s$ 关联。也就是说不同的 $s$ 映射到不同的 $t$。

    ![image.png](/static/img/e7d3bdccb8c5ea4277d6ff8edab77e52.image.webp)
- 满射（Sur） surjective：对于每个 $T$ 中的元素 $t$，在关系 $R$ 中至少与一个 $S$ 中的元素 $s$ 关联。也就是说 $T$ 中的每个元素都是某个 $s$ 的映射。

    ![image.png](/static/img/77254c6d4ba4aa80aeec972f67fa9a89.image.webp)
- 双射（Bij） bijective：关系 $R$ 同时满足单射和满射。也就是说，$S$ 到 $T$ 的映射是一对一的（每个 $s$ 只能映射到一个独特的 $t$），并且是覆盖的（$T$ 中的每一个 $t$ 都被 $S$ 中的某个 $s$ 映射到）。
    
    ![image.png](/static/img/6e8f65ee5fe3c87f6567da6e6d1885ef.image.webp)


## 同一集合上的二元关系性质 Properties of Binary Relations $R \subseteq S \times S$

- 自反性（R）reflexive：对于集合 $S$ 中的所有元素 $x$，都有 $(x,x) \in R$。也就是说，每个元素都与自己本身在关系 $R$ 中有关联。
- 反自反性（AR）antireflexive：对于集合 $S$ 中的所有元素 $x$，都有 $(x,x) \notin R$。也就是说，没有任何元素与自己本身在关系 $R$ 中有关联。
- 对称性（S）symmetric：如果有序对 $(x,y) \in R$，且 $(y,x) \in R$。
- 反对称性（AS）antisymmetric：如果有序对 $(x,y)$ 和 $(y,x)$ 都在 $R$ 中，必须有 $x=y$。
- 传递性（T）transitive：如果有序对 $(x,y)$ 和 $(y,z)$ 都属于关系 $R$，那么 $(x,z) \in R$。

如果某关系具有该性质，意味着这些性质是对关系中的所有元素都成立的。

其中，S，AS，T是条件语句，如果没有任何元素满足“如果”部分的条件，那么属性被认为是成立的。例如，如果在关系中不存在任何两个不同元素 
$x, y$使得 $(x,y)$ 和 $(y,x)$ 同时存在，那么该关系就被视为反对称的。

## 性质的交互 Interaction of Properties

一个关系可以同时是对称的和反对称的。这种情况发生在关系 
$R$ 仅由形如 $(x,x)$ 的有序对组成时，也就是说，除了自反元素之外没有其他元素。在这种情况下，每个元素与自己相关联，但没有不同的元素 $x,y$ 使得 $(x,y)$ 和 $(y,x)$ 同时在 $R$ 中。

关系不能同时是自反的和反自反的，除非集合 $S$ 是空集。这是因为自反性要求集合 $S$ 中每个元素与自己相关联，而反自反性要求没有任何元素与自己相关联，这两个定义是相互矛盾的。

不具有自反性（nonreflexive）或不具有对称性（nonsymmetric）的关系，不等同于反自反的（antireflexive/irreflexive）或反对称的（antisymmetric）关系。这是关系属性的一个重要区别，因为“不具有某属性”（如不自反或不对称）并不一定意味着它具有对应的“反属性”（如反自反或反对称）。

例如，一个关系，如果它对某些元素是自反的，而对其他元素则不是自反的，那么该关系既不是自反的也不是反自反的。


# 数学函数 Functions

一个函数 $f:S→T$，是从集合 $S$ 到集合 $T$ 的一个二元关系 $f \subseteq S \times T$，且满足函数式（Fun）和全域性（Tot）两个属性。也就是说，对于集合 $S$ 中的每一个元素 $s$，都有且只有一个元素 $t$ 在集合 $T$ 中与之关联。

如果 $s$ 唯一关联 $t$，我们用 $f(s)$ 来表示 这个唯一关联的 $t$。

我们用函数集 $T^S$ 表示从 $S$ 到 $T$ 的所有可能的函数的集合。


![image.png](/static/img/7cba91a32f4805b2708cb27fcd5c3477.image.webp)

### 术语

1. 定义域（domain），包含所有可能的输入，即集合 $S$。
2. 上域（co-domain），包含所有可能的输出，即集合 $T$。
3. 像（image），即值域（range），是函数 $f$ 的实际所有输出，为 $T$ 的子集。

###  符号

1. 定义域：$Dom(f)$
2. 上域：$Codom(f)$
3. 像：$Im(f)$，也可写作 $\{ f(x): x \in Dom(f) \}$

### 要点

定义域，上域，方法，三者完全相同的，才能认为是相同的函数。不同的定义域/上域，会影响函数的性质和应用。

当函数 $f$ 同时满足单射和满射（即双射，或称一一对应函数）时， 关系 $f^←$ 才能也是一个函数。

## 双射的性质 Properties of bijections

1. 如果 $f: S → T$ 和 $g: T → U$ 是双射，那么它们的逆函数也是双射的。
2. 函数 $f$ 和 $g$ 的复合 $(f;g): S → U$ 也是双射。
3. 函数 $f$ 与它的逆函数 $f^←$ 的复合等于在 $S$ 上的恒等关系，记作 $f;f^←=I_S$，它包含所有形如 $(x,x)$ 的元素对，其中 $x \in S$。
4. 逆函数 $f^←$ 与函数 $f$ 的符合等于在 $T$ 上的恒等关系，记作 $f^←;f=I_T$，它包含所有形如 $(x,x)$ 的元素对，其中 $x \in T$。

最后两个性质实际上定义了双射函数的逆函数关系，也就是说，你可以通过 $f$ 找到 $T$ 中的每个元素的原像，反过来通过 $g$ 找到 $S$ 中的每个元素的原像，没有遗漏也没有重复。


![image.png](/static/img/c17180b21ba75d2d7ed59d21e8d7149a.image.webp)

COMP9020 4.1 Relations

发布于2022年的reddit：《How much do game developers in Australia make?》。




[原文地址](https://www.reddit.com/r/cscareerquestionsOCE/comments/qaedtk/how_much_do_game_developers_in_australia_make/)

# 正文

> 注：在本文中，OP指发帖人的ID。Posted by u/SaxOps1

嘿，OP，我在2018年底毕业时，也几乎遭遇了和你一样的情况。你可以查看我的发帖记录来确认，因为我很少用这个账户发帖。基本来说，你几乎什么钱都赚不到。游戏开发是一个娱乐领域，然而，如果你想赚钱， 你就不该入局。与其他娱乐媒介不同，非常不幸，除了变成极少数公司的创始人，你甚至没法脱颖而出成为一个明星制作人，成为一个能赚到大钱的极少数人。我认识一些在游戏开发领域工作了十数年的人，他们的收入甚至还没到我刚毕业的时候。话虽如此，还是会有一些公司会支付给你体面的薪水，虽然比不上那些大科技公司，但比起其他工作室的待遇绝对要好一些。我能想到的有ROIT GAMES、ROBLOX和UNITY。但我需要强调，这样的公司少之又少。

这种情况是国际性的。如果你专注于澳大利亚，那么游戏开发在这里几乎等同于死路一条。几年前曾经有一些大的游戏公司，但最后都因为政府削减游戏开发资金等原因而夭折。与大多数国家相比，在这里建立工作室没有经济激励。不过，仍然有一些工作室存在在这里。墨尔本的TANTALUS（如今几乎只移植游戏）、墨尔本的EA工作室（FIREMONKEYS）和悉尼的WarGaming是剩下的几家大工作室。这些公司的职业空缺并不多，而且因为它们基本上是这里唯一的游戏工作室，所以每个想从事游戏开发的人都在竞争这些职位。这里还有一些独立工作室。这些工作室可能会更难进，因为他们没有足够的资金聘用很多开发人员，很可能会聘用自己认识的人。

关于薪资，我有一个来自悉尼WarGaming公司的实习offer（当时他们还没有管培生招聘，当然我想现在应该也很少），2018年底的全职薪资是5万澳币。这与最低工资标准相差无几，这是可是个技术岗位，而且你很可能还需要用它来偿还学生贷款，因此这并不理想。我想在他们那里，初级职位的工资也不会高到哪里去。我在他们之前的两份实习工作的工资都要高得多。

你可以选择到海外从事游戏工作，但这也会非常困难。海外游戏工作室确实会在国际范围内招聘，并为你的签证提供担保，但要记住，这对于刚刚毕业的学生来说不太可能。这些职位的需求量并不大，而且还会有很多本地的申请者。说说我的故事吧，我在维基百科上找到了一份游戏工作室的名单，并向每一家工作室提出了申请。仅有的几家直接回复我说他们不会聘用我——这意味着我的简历甚至没能通过筛选，其他的工作室更是了无音讯。

如果认为你就是为游戏而生的，我不会劝你放弃，但你真的要好好考虑一下。扪心自问，你是否真的想这样做。我曾经和你一样。我从8岁开始做游戏开发，在高中和大学快毕业时利用业余时间编写游戏引擎，痴迷于实现新的花哨的图形算法。我曾经认为我真的会从事游戏开发，因为那是我的使命。我幻想着要么成立自己的工作室，要么先给别人打工，然后再转行做游戏开发。我知道薪水低、工作时间长（项目的关键节点时尤甚），但我不在乎，因为我想做游戏。当我向所有这些工作室提出申请却没有任何回音时，我非常沮丧，我真的没别的工作室可以申请了。随着年龄的增长，我逐渐意识到自己没能进入任何一家工作室是不幸中的万幸。真正的现实是，你很可能会从事一些并不光彩、没有影响力或没有乐趣的工作。在项目的要紧时间，你的生活中最要命的东西可能就是你手头上的工作。此外，工作可能会让你失去所有对生活的乐趣。我目前在悉尼一家科技公司从事渲染技术工作，收入是悉尼一家游戏公司的10倍，我正在做的项目也与我喜欢的游戏开发的一些东西有些吻合。扪心自问一下，你是否愿意付出极大的代价从事游戏开发工作，因为这基本上就是走上这条路的必然结果。对我来说，我无法回答 "是"。

这篇文章真的很长，但我写这篇文章就像是在和3年前的自己对话。如果你有任何问题，请随时联系我。

# 原文

Hey OP, posting here because I was in the exact same situation when I graduated end of 2018 (you could probably check my posts on here to verify that since I don't post much on this account). Basically the gist of it is you'd get barely anything. Game dev is an entertainment field, you should not go into it if you want to make money. Unfortunately, unlike other entertainment mediums, there's not even a way to stand out like a celebrity and have at least a very small portion of the people making a lot (aside from founders in a very few of the companies). For context, I know people that have worked 10+ years in gamedev and still make less than I did as a grad. That being said, there are some companies that will pay somewhat decently. You still won't be making as much as you would at a normal big tech company but it's definitely better. Some that come to mind are riot games, roblox, unity. I want to stress that these companies are few and far between.

That's internationally though, if you're focusing on Australia game development is pretty much dead here. There used to be a few big name companies years ago but they all died after government funding cuts for game development here among other things. There's no real financial incentive to setup a studio here compared to most other countries. There's still a few studios around though. There's tantalus in Melbourne (which pretty much just do ports these days), an EA studio Melbourne working on mobile apps/engines (Firemonkeys) and WarGaming in sydney to name the big ones left. There aren't many job openings at these companies and since they're basically the only game studios here, everyone that wants to work in game dev is competing for them. There's also a few indie studios here too. These would likely be even harder to get into as they don't really have the funding for many developers and likely will hire people they know.

In terms of salaries, for some tangible numbers, I had an internship offer from wargaming sydney (they weren't offering grad roles at the time and I think it's very rare that they do) for 50k full time at the end of 2018. That's not that far off minimum wage, which for a skilled position and one you likely will be using to pay off your student debt, isn't ideal. I assume a junior role wouldn't be much more with them. Both internships I had before them paid a lot more.

You can take the route of moving overseas to work on games, but it too is going to be insanely hard. Overseas game studios do hire internationally and sponsor visas, but keep in mind that it's very unlikely for a grad role. These roles are not really in demand and will have a lot of local applicants. To give you my story, I went through a wikipedia list of game studios and applied to every single one. The only ones that got back to me said they wouldn't hire me (didn't even make it pass the resume screening for any of them) and the rest I heard nothing from.

If your passion is working on games for a living, I'm not going to dissuade you from doing it but really do think about it. Ask yourself if you really want to do it. I used to be like you. I started game dev when I was 8, wrote game engines in my spare time towards the end of highschool and uni, was obsessed with implementing the new fancy graphics algorithms, ect. I thought I was really committed to doing game dev and it was my calling. I was either going to start my own studio or start by working for someone else and then pivot to it. I knew about the bad pay and longer hours (crunch time is real) but I didn't care because I wanted to work on games. I was so depressed when I was hearing nothing back from applying to all these studios (I literally ran out of places to apply). As I've gotten older I've realised it was a blessing in disguise that I never got into any of them. The reality is you'd likely be working on things that aren't that glamorous or impactful or fun. It's going to be working on what's the most required thing for the project at the given time. Furthermore, having a job will probably suck all enjoyment you get out of it. I'm currently working at a Sydney tech company on rendering tech and making 10x minimum what I would at a game company in sydney. The project I'm on also somewhat aligns with some of the things I loved about game development. Really ask yourself if you would want to be paying large sums of money to be working in gamedev, since that's essentially what you would be doing. For me I can't answer yes to that.

This is really long, but I'm basically writing this as though I'm talking to myself from 3 years ago. If you have any questions feel free to reach out.

Reddit：澳大利亚的游戏产业

QUIZ 3



## 1.1

### Question

Consider the graph with:

- vertex set `{0,1}×{0,1}×{0,1}`
- an edge between two vertices if they differ in exactly two co-ordinates

What is the degree sequence of this graph?

Select one alternative:
```
- 1,1,1,1,1,1,1,1
- 0,0,2,2,2,2,0,0
- 0,4,4,0,0,00,0,0
- 0,0,0,8,0,0,0,0
- None of the above
```

### Answer

首先这是一个无向图。

其次，这个顶点集的坐标是一个三阶向量，每一位都由0或1组成。因此，顶点有如下几种：

```
(0,0,0) (0,0,1) (0,1,0) (0,1,1)
(1,0,0) (1,0,1) (1,1,0) (1,1,1)
```

现在，对相互之间位数差异位2的点互相连线以构成边，所以只需要考虑哪些点跟其相差有2即可。

但换句话说，这也可以考虑保留一位，另外两位都不同即可。而每一个坐标一共有三位，所以每个点都可以与另外三个点进行连线，换句话说每个点都有三个度。


因此，答案为：

```
3,3,3,3,3,3,3,3

None of the above
```

## 1.2

### Question

Which of the following graphs are isomorphic to this graph:


![image.png](/static/img/0132668af49c922b1c60355f366a7b61.image.webp)

Select all that apply:

![](https://rin977.com/static/img/ae6b3fb5bcdab36f7eb61c3782c35620.image.webp)


![image.png](/static/img/f74cee2ec14b0b0e6a92f80c6e2a88a8.image.webp)


![image.png](/static/img/a5ab3d8e5078ce0d32a29ed5ff9d31c6.image.webp)


![image.png](/static/img/bc708ed6cfa8a3b812c3412ad3355496.image.webp)


![image.png](/static/img/264638bb00a7d94b9f9f01f289f8526b.image.webp)


![image.png](/static/img/531de2d2f162c2d85e73a4f320917698.image.webp)

### Answer

画图，设点，一点点推，找到矛盾边、矛盾点即可排除。

答案为：

![image.png](/static/img/f74cee2ec14b0b0e6a92f80c6e2a88a8.image.webp)

![image.png](/static/img/264638bb00a7d94b9f9f01f289f8526b.image.webp)

## 1.3

### Question

Starting from Vertex 0, which of the following sequences of vertices could arise as a sequence of explored vertices when performing a breadth-first traversal (according to lectures)?


![image.png](/static/img/5519dee7d403fd49163d96441f51c392.image.webp)

Select all that apply:

```
- 0,2,1,3,5,4,8,6,7
- 0,1,2,3,6,5,4,7,8
- 0,3,2,1,4,5,6,8,7
- 0,3,5,8,7,6,4,2,1
- 0,1,3,4,5,8,7,6,2
- 0,1,2,3,4,5,6,7,8
```

### Answer

该图像的同构如图所示：

```
        0
     /  |  \
    3 - 2 - 1
  / |   |
4 - 5   6
    |   |
    8 - 7
```

则根据广度优先算法，我们应当为每一层先进行遍历，再进行下一层。

答案为：

```
- 0,1,2,3,6,5,4,7,8
- 0,3,2,1,4,5,6,8,7
- 0,1,2,3,4,5,6,7,8
```

## 1.4

### Question

Starting from Vertex 0, which of the following sequences of vertices could arise as a sequence of explored vertices when performing a depth-first traversal (according to lectures)?

![image.png](/static/img/5519dee7d403fd49163d96441f51c392.image.webp)

Select all that apply:

```
- 0,1,3,4,5,8,7,6,2
- 0,3,2,1,4,5,6,8,7
- 0,2,1,3,5,4,8,6,7
- 0,3,5,8,7,6,4,2,1
- 0,1,2,3,6,5,4,7,8
- 0,1,2,3,4,5,6,7,8
```

### Answer

可以自己画图试验一下，一个一个试即可。注意：需要给每一个还未遍历但已经被父节点发现的点标注深度，并且一个点不能被重复标注深度。

答案为：

```
- 0,1,3,4,5,8,7,6,2
- 0,3,5,8,7,6,4,2,1
```

## 1.5

### Question

Which of the following properties does this graph have?


![image.png](/static/img/a85a872eed9e5364d6aacd93b72a7aee.image.webp)

Select all that apply:

```
- Contains a cycle of length 10
- Bipartite
- Planar
- Hamiltonian path
- Connected
- Chromatic number 3
- Clique number 2
- Eulerian path
```

### Answer

首先为图中的每个点标注序号，方便进行表示。


![0f56485d2899a9d2f2e5b0f3f62f0bdd.png](/static/img/edd7c289e77ade337b8e3b32e1024eac.0f56485d2899a9d2f2e5b0f3f62f0bdd.webp)

- 选项1：循环路径如下。

$$
1 \to 2 \to 3 \to 10 \to 7 \to 5 \to 8 \to 11 \to 9 \to 4 \to 1
$$

- 选项2：通过染色法可尝试证明。如果图能被着成二色，说明是二分的。

$$
black: [1] \\
white: [2, 4, 5, 6] \\
black: [3, 7, 8, 9] \\
white: [10, 11] \\
$$

- 选项3：显然它没有任何的边有相交，因此它是平面的。
- 选项4：不存在，难以证明，但确实不存在。
- 选项5：正确的，每一对顶点都存在路径到达。
- 选项6：上文以证明，色数为2。
- 选项7：由于色数大于等于团数，因此团数最大为2。而找到一条边即包含两个顶点，因此团数可以为2。
- 选项8：对于连通图来说，存在欧拉路径的条件式每个点的度数为偶数或恰好两个顶点的度数是奇数。显然，2, 4, 5, 6, 7, 9, 10, 11的度数都为基数，因此不存在欧拉路径。

因此，答案为：

```
- Contains a cycle of length 10
- Bipartite
- Planar
- Connected
- Clique number 2
```

## 2.1

### Question

Which of the following statements are true for any graph with n≥1 vertices and m≥0 edges?

Select all that apply:

```
- If m < n then the graph is acyclic
- If m ≥ n-1 then the graph is connected
- If m ≥ n then the graph contains a cycle
- If m < n-1 then the graph is not connected
```

### Answer

- 选项1：错误。例如，当前有一个点离散在外，另外n-1个点首尾相接，满足m=n-1<n，然而该图具有环。
- 选项2：错误。例如，当前有一个点离散在外，另外n-1个点首尾相接，满足m=n-1，然而该图并不连通。
- 选项3：正确。在一个有 n 个顶点的图中，如果有至少 n 条边，那么至少有一个顶点的度数大于 1，这意味着在这些顶点中形成了一个环。因为一棵树（没有环的连通图）恰好有 n-1 条边，所以任何边数超过 n-1 的图至少有一个环。
- 选项4：正确。一个有 n 个顶点的图要形成连通图，至少需要 n-1 条边来形成一棵树（树是最少边数的连通图）。如果边的数目少于 n-1，那么一定存在至少一个顶点与图的其他部分不连通。

因此，答案为：

```
- If m ≥ n then the graph contains a cycle
- If m < n-1 then the graph is not connected
```

## 2.2

### Question


Let D0, D1, D2, D3 be the degree sequence of a tree with n≥2 vertices (assume Dk = 0 for k≥4)

Which of the following must necessarily hold:

Select all that apply

```
- D1 is even
- D3 ≥ D2
- D2 ≥ D3
- D1 = 2 + D3
- D0 = 0
- D1 ≥ 2
```

### Answer

对于一棵有 n 个顶点的树，以下性质始终成立：

- 它有 n-1 条边。
- 至少有两个顶点的度数是 1（也就是说，至少有两个叶子节点）。
- 树中没有度数为 0 的顶点，因为树是连通的。

由于在大于等于4的情况下，Dk=0，我们可以认为没有度数大于等于4的节点。

---

- 选项1：错误。至少有两个顶点度数是1，但不一定意味着一直都是偶数。反例如下，D1=3
  ```
   o  o  o
   |  |  |
   o  o  o
    \ | /
      o
  ```
- 选项2：错误。反例如下，D3=1，D2=3
  ```
   o  o  o
   |  |  |
   o  o  o
    \ | /
      o
  ```
- 选项3：错误。反例如下，D3=1，D2=0
  ```
   o  o  o
    \ | /
      o
  ```
- 选项4：正确。设一棵树T有n个顶点，那么它有n-1条边，度数总数则为2(n-1) = 2n-4。由于树没有环，所以每增加一个度数为3的顶点，必须至少增加两个度数为1的顶点（叶子节点）来保持树的结构。这是因为度数为3的顶点在不增加环的情况下提供了两个额外的边缘连接点，这些连接点必须由叶子节点来平衡，因为叶子节点只会增加一个连接点。
- 选项5：正确。树是连通的，因此不存在度数为0的点。
- 选项6：正确。树中至少有两个叶子结点。


因此，答案为：

```
- D1 = 2 + D3
- D0 = 0
- D1 ≥ 2
```

## 2.3

### Question


Which of the following graphs have an Eulerian circuit?

Select all that apply

- $K_{5,5}$
- All graphs with degree sequence 0,0,5,0,5
- All regular graphs with 5 vertices and 10 edges
- All graphs with degree sequence 0,0,3,0,3,0,3
- $K_5$
- $K_{5,5,5}$

### Answer

存在欧拉回路的条件：

1. 所有的点的度数都为偶数。
2. 不满足1，那么需要恰好有两个点的度数为奇数。

- 选项1：错误。由于每一个点都和另外集合内所有点有对应关系，因此所有的点的度数都为5。
- 选项2：错误。不连通。
- 选项3：正确。由于10 = 5*(5-1)，所以这个图是一个完全图。每一个点的度数均为5-1=4。
- 选项4：错误。不连通。
- 选项5：正确。这个图是一个完全图。每一个点的度数均为5-1=4。
- 选项6：正确。这个图是一个完全三部图，每一个点的度数为5+5=10。

因此，答案为：

```
- All regular graphs with 5 vertices and 10 edges
- K_5
- K_{5,5,5}
```

## 2.4

### Question


Let G be a finite directed graph where every vertex has in-degree and out-degree at most 1.

True or false:

G has a vertex of out-degree 0 if and only if G has a vertex of in-degree 0.

### Answer

在一个有限的有向图G中，如果每个顶点的入度和出度最多为1，这意味着每个顶点要么与一个其他顶点相连（作为其唯一的前驱或后继），要么完全不与任何顶点相连（入度和出度都为0）。

为了理解为什么这个陈述是真的，我们可以考虑以下情况：

如果G有一个出度为0的顶点，那么这意味着有一个顶点没有指向任何其他顶点的边。由于图是有限的，并且每个顶点的连接数是受限的（最多1个出度和1个入度），这意味着必须有至少一个顶点的入度为0，因为否则会形成一个封闭的环，使得每个顶点都有出度和入度，这与假设矛盾。

反过来，如果G有一个入度为0的顶点，这意味着有一个顶点没有任何从其他顶点指向它的边。考虑到图中顶点数量有限，以及每个顶点的连接数受限，这就意味着必须有至少一个顶点的出度为0，以防止形成一个完全封闭的环路。否则，如果每个顶点都有一个出度，那么每个顶点也必须有一个入度，以保持平衡，这会导致每个顶点既是某个环的一部分，又是该环的出发点，这与入度为0的假设矛盾。

因此，这个陈述展示了在这种类型的图中，出度为0的顶点的存在必然意味着有一个入度为0的顶点的存在，反之亦然。这是由于图的有限性和每个顶点入度及出度的限制共同决定的。

因此，答案为：

```
True
```

## 2.5

### Question

True or false:

If a graph has chromatic number at least 3, then it must contain a subdivision of K3

### Answer

显然错误。一个环图如果有奇数个点，那么它的色数必然等于3，然而一个环图并不一定是 $K_3$。

因此，答案为：

```
False
```